상경한 개발자 지망생들

문제 설명

레스토랑을 운영하던 스카피는 코로나19로 인한 불경기를 극복하고자 메뉴를 새로 구성하려고 고민하고 있습니다.
기존에는 단품으로만 제공하던 메뉴를 조합해서 코스요리 형태로 재구성해서 새로운 메뉴를 제공하기로 결정했습니다. 어떤 단품메뉴들을 조합해서 코스요리 메뉴로 구성하면 좋을 지 고민하던 "스카피"는 이전에 각 손님들이 주문할 때 가장 많이 함께 주문한 단품메뉴들을 코스요리 메뉴로 구성하기로 했습니다.
단, 코스요리 메뉴는 최소 2가지 이상의 단품메뉴로 구성하려고 합니다. 또한, 최소 2명 이상의 손님으로부터 주문된 단품메뉴 조합에 대해서만 코스요리 메뉴 후보에 포함하기로 했습니다.

예를 들어, 손님 6명이 주문한 단품메뉴들의 조합이 다음과 같다면,
(각 손님은 단품메뉴를 2개 이상 주문해야 하며, 각 단품메뉴는 A ~ Z의 알파벳 대문자로 표기합니다.)

손님 번호주문한 단품메뉴 조합

가장 많이 함께 주문된 단품메뉴 조합에 따라 "스카피"가 만들게 될 코스요리 메뉴 구성 후보는 다음과 같습니다.

코스 종류메뉴 구성설명

[문제]

각 손님들이 주문한 단품메뉴들이 문자열 형식으로 담긴 배열 orders, "스카피"가 추가하고 싶어하는 코스요리를 구성하는 단품메뉴들의 갯수가 담긴 배열 course가 매개변수로 주어질 때, "스카피"가 새로 추가하게 될 코스요리의 메뉴 구성을 문자열 형태로 배열에 담아 return 하도록 solution 함수를 완성해 주세요.

[제한사항]

• orders 배열의 크기는 2 이상 20 이하입니다.
• orders 배열의 각 원소는 크기가 2 이상 10 이하인 문자열입니다.
  • 각 문자열은 알파벳 대문자로만 이루어져 있습니다.
  • 각 문자열에는 같은 알파벳이 중복해서 들어있지 않습니다.
• course 배열의 크기는 1 이상 10 이하입니다.
  • course 배열의 각 원소는 2 이상 10 이하인 자연수가 오름차순으로 정렬되어 있습니다.
  • course 배열에는 같은 값이 중복해서 들어있지 않습니다.
• 정답은 각 코스요리 메뉴의 구성을 문자열 형식으로 배열에 담아 사전 순으로 오름차순 정렬해서 return 해주세요.
  • 배열의 각 원소에 저장된 문자열 또한 알파벳 오름차순으로 정렬되어야 합니다.
  • 만약 가장 많이 함께 주문된 메뉴 구성이 여러 개라면, 모두 배열에 담아 return 하면 됩니다.
  • orders와 course 매개변수는 return 하는 배열의 길이가 1 이상이 되도록 주어집니다.

[입출력 예]

orderscourseresult

입출력 예에 대한 설명

입출력 예 #1
문제의 예시와 같습니다.

입출력 예 #2
AD가 세 번, CD가 세 번, ACD가 두 번, ADE가 두 번, XYZ 가 두 번 주문됐습니다.
요리 5개를 주문한 손님이 1명 있지만, 최소 2명 이상의 손님에게서 주문된 구성만 코스요리 후보에 들어가므로, 요리 5개로 구성된 코스요리는 새로 추가하지 않습니다.

입출력 예 #3
WX가 두 번, XY가 두 번 주문됐습니다.
3명의 손님 모두 단품메뉴를 3개씩 주문했지만, 최소 2명 이상의 손님에게서 주문된 구성만 코스요리 후보에 들어가므로, 요리 3개로 구성된 코스요리는 새로 추가하지 않습니다.
또, 단품메뉴를 4개 이상 주문한 손님은 없으므로, 요리 4개로 구성된 코스요리 또한 새로 추가하지 않습니다.

접근 방법

 HashMap과 backTracking을 적절히 활용하여 해결할 수 있는 문제였습니다.

1. 문제를 해결하기에 앞서 orders를 정렬 해야합니다. 한 예시로 xy와 yx는 같은 조합으로 볼 수 있고, 이러한 경우를 수월하게 계산하기 위해 사전순으로 정렬합니다.

2. 최소 2번 이상 주문된 음식의 조합(backTracking)을 HashMap에 저장합니다. (HashMap<String 음식조합, Integer 주문횟수>) 

3. HashMap의 원소를 각각 탐색하면서 음식조합의 수가 course의 한 요소와 일치한다면 가장 많이 주문된 횟수를 비교 갱신하며 음식조합 또한 추가 혹은 갱신을 합니다. 이 때 아래 2개의 HashMap을 사용하였습니다.

 (1) HashMap<Integer, ArrayList<String>> maxMap = new HashMap<Integer, ArrayList<String>>(); 
 (2) HashMap<Integer, Integer> maxCnt = new HashMap<Integer, Integer>();  

maxMap은 음식조합의 수(course)에 따른 음식조합을 저장합니다. 만약 한 음식 조합의 주문된 횟수가 최대 주문 횟수랑 일치하는 경우 요소를 추가해야 하기 때문에 value는 List의 형태를 가져야 합니다.

maxCnt는 음식조합의 수(course)에  따른 주문된 최대 횟수를 저장합니다.

자세한 내용은 아래 소스코드에 주석으로 설명하겠습니다.

소스 코드

import java.util.*;
import java.lang.*;

class Solution {
    
    HashMap<String, Integer> map = new HashMap<String, Integer>();
    HashMap<Integer, ArrayList<String>> maxMap = new HashMap<Integer, ArrayList<String>>(); 
    HashMap<Integer, Integer> maxCnt = new HashMap<Integer, Integer>(); 
    
    public void backTracking(int n, int cnt, int now, String order, String comb){
        
        if(cnt == n){
            if(map.containsKey(comb)){ //이미 주문된 적 있는 조합이라면
                int orderCnt = map.get(comb);
                map.put(comb, orderCnt + 1); // 주문횟수 1증가
            }
            else
                map.put(comb, 1);
        }
        for(int i = now; i<order.length(); i++){
            comb += order.charAt(i);
            backTracking(n, cnt+1, i + 1, order, comb);
            comb = comb.substring(0, comb.length() - 1);
        }
    }
    
    public ArrayList<String> solve(String[] orders, int[] course){
        
        ArrayList<String> ans = new ArrayList<String>();
        
        //1번 과정, 수월한 풀이를 위해 문자열 사전순 정렬
        for(int i=0;i<orders.length;i++){
            char[] tmp = orders[i].toCharArray();
            Arrays.sort(tmp);
            orders[i] = new String(tmp);
        }
        
        //2번 과정, i번째 주문에 대해 ,j개(최소 2개) 이상의 조합을 구함
        for(int i=0;i<orders.length;i++)
            for(int j=2;j<=orders[i].length();j++)
                backTracking(j,0,0,orders[i], "");    
        
        //course를 map에 미리 매핑시킴, 이후 course의 요소인지 판별하기에 쉽게 이용 가능
        for(int i=0;i<course.length;i++){
            maxMap.put(course[i], new ArrayList<String>()); 
            maxCnt.put(course[i], 0); 
        }
        
        //3번 과정
        for(Map.Entry<String, Integer> elem : map.entrySet()){
            String foods = elem.getKey();
            int cnt = elem.getValue();
            if(cnt >= 2){
                if(maxMap.containsKey(foods.length())){ //course의 요소라면
                    if(maxCnt.get(foods.length()) == cnt){ //최대 주문 횟수와 일치한다면
                        maxMap.get(foods.length()).add(foods); //추가
                    }
                    else if(maxCnt.get(foods.length()) < cnt){ //최대 주문 횟수 보다 더 크다면
                        maxCnt.put(foods.length(), cnt); //최댓값 갱신
                        ArrayList<String> newOne = new ArrayList<String>(Arrays.asList(foods)); 
                        maxMap.put(foods.length(), newOne); //새롭게 갱신
                    }
                }
            }   
        }
        
        //결과들을 ArrayList에 담는다.
        for(ArrayList<String> elem : maxMap.values())
            for(int i=0;i<elem.size();i++)
                ans.add(elem.get(i));    
        
        //사전순 정렬
        Collections.sort(ans);
        
        return ans;
    }
    
    public String[] solution(String[] orders, int[] course) {
        ArrayList<String> ans = solve(orders, course);
        String[] answer = ans.toArray(new String[ans.size()]);
        return answer;
    }
}

문제 설명

자동완성

포털 다음에서 검색어 자동완성 기능을 넣고 싶은 라이언은 한 번 입력된 문자열을 학습해서 다음 입력 때 활용하고 싶어 졌다. 예를 들어, go 가 한 번 입력되었다면, 다음 사용자는 g 만 입력해도 go를 추천해주므로 o를 입력할 필요가 없어진다! 단, 학습에 사용된 단어들 중 앞부분이 같은 경우에는 어쩔 수 없이 다른 문자가 나올 때까지 입력을 해야 한다.
효과가 얼마나 좋을지 알고 싶은 라이언은 학습된 단어들을 찾을 때 몇 글자를 입력해야 하는지 궁금해졌다.

예를 들어, 학습된 단어들이 아래와 같을 때

go gone guild

• go를 찾을 때 go를 모두 입력해야 한다.
• gone을 찾을 때 gon 까지 입력해야 한다. (gon이 입력되기 전까지는 go 인지 gone인지 확신할 수 없다.)
• guild를 찾을 때는 gu 까지만 입력하면 guild가 완성된다.

이 경우 총 입력해야 할 문자의 수는 7이다.

라이언을 도와 위와 같이 문자열이 입력으로 주어지면 학습을 시킨 후, 학습된 단어들을 순서대로 찾을 때 몇 개의 문자를 입력하면 되는지 계산하는 프로그램을 만들어보자.

입력 형식

학습과 검색에 사용될 중복 없는 단어 N개가 주어진다.
모든 단어는 알파벳 소문자로 구성되며 단어의 수 N과 단어들의 길이의 총합 L의 범위는 다음과 같다.

• 2 <= N <= 100,000
• 2 <= L <= 1,000,000

출력 형식

단어를 찾을 때 입력해야 할 총 문자수를 리턴한다.

입출력 예제

wordsresult

입출력 설명

• 첫 번째 예제는 본문 설명과 같다.
• 두 번째 예제에서는 모든 단어들이 공통된 부분이 없으므로, 가장 앞글자만 입력하면 된다.
• 세 번째 예제는 총 15 자를 입력해야 하고 설명은 아래와 같다.
  • word는 word모두 입력해야 한다.
  • war는 war 까지 모두 입력해야 한다.
  • warrior는 warr 까지만 입력하면 된다.
  • world는 worl까지 입력해야 한다. (word와 구분되어야 함을 명심하자)

접근 방법

 Trie 자료구조를 공부해봤다면 문제를 봤을 때 Trie를 사용해 해결할 수 있다는 것을 바로 떠올릴 수 있었을 것입니다.

 저는 문제를 풀기 위해 Trie의 한 노드가 가지는 자료를 3가지를 정의하였습니다.

1. child HashMap<Character, Node> child = new HashMap();

2. boolean isEnd;

3. int branchSum;

1번 child는 노드의 child노드를 연결하기 위한 링크 역할을 합니다.

2번 isEnd는 단어의 끝인지의 여부를 나타냅니다.

3번 branchSum은 뻗어있는 가지의 수를 의미합니다. (isEnd == true)인 구간, 즉 단어의 끝을 가지는 부분도 하나의 가지로 계산합니다.

만약 단어가 go, gone, guild가 주어진다면 branchSum의 상태는 아래의 그림과 같습니다.

아래와 같은 코드로 branchSum을 계산할 수 있습니다.

public int makeBranchSum(Node now){

	if(now.isEnd && now.child.isEmpty()) //단어의 끝이면서 더 나아갈 깊이가 없는 경우
		return now.branchSum = 1;

	for(Node node : now.child.values())
		now.branchSum += makeBranchSum(node);

	//단어의 끝이지만 더 나아갈 깊이가 있는 경우, 위 그림에서 노드(o)에 해당
	if(now.isEnd && !now.child.isEmpty()) 
		now.branchSum += 1;
	return now.branchSum;
} 

 isEnd와 branchSum을 적절히 활용하면 문제를 해결할 수 있습니다.

1. 일단 처음으로 (branchSum == 1)인 구간에 도달한다면 더 이상의 가지가 뻗어있지 않다는 의미가 되므로 그 구간까지의 깊이를 반환하고, 더 깊은 곳으로 진입하지 않습니다.

2. 만약 branchSum != 1이고 isEnd == true인 경우면 더 나아갈 수 있는 가지는 남아있으나, 여기가 어떠한 단어의 끝이라는 의미가 되므로 그 구간까지의 깊이를 포함하여 더해줍니다.

public int search(Node now, int cnt){ //cnt는 깊이를 의미
        
	int ret = 0;

	if(now.branchSum == 1) //1번 항목 검사
		return cnt;

	for(Node node : now.child.values())
		ret += search(node, cnt + 1);
	if(now.isEnd) //2번 항목 검사
		ret += cnt;

	return ret;
}

소스 코드

import java.util.*;

class Solution {
    
    public class Node {
        HashMap<Character, Node> child = new HashMap();
        boolean isEnd = false;
        int branchSum = 0;
    }
    
    public class Trie {
        
        Node root;
        
        public Trie(){
            root = new Node();
        }
        
        public void insert(String word){
            
            Node current = root;
            
            for(Character c : word.toCharArray()){
                if(current.child.get(c) == null){
                    Node node = new Node();
                    current.child.put(c, node);
                    current = node;
                }
                else
                    current = current.child.get(c);
            }
            current.isEnd = true;
        }
    }
    
    public int makeBranchSum(Node now){
        
        if(now.isEnd && now.child.isEmpty())
            return now.branchSum = 1;
        
        for(Node node : now.child.values())
            now.branchSum += makeBranchSum(node);
        
        if(now.isEnd && !now.child.isEmpty())
            now.branchSum += 1;
        return now.branchSum;
    } 
    
    public int search(Node now, int cnt){
        
        int ret = 0;
        
        if(now.branchSum == 1)
            return cnt;
        
        for(Node node : now.child.values())
            ret += search(node, cnt + 1);
        if(now.isEnd)
            ret += cnt;
        
        return ret;
    }
    
    public int solve(String[] words){
        
        Trie trie = new Trie();
        
        for(int i=0;i<words.length;i++){
            String word = words[i];
            trie.insert(word);
        }
        makeBranchSum(trie.root);
        return search(trie.root, 0);
    }
    
    public int solution(String[] words) {
        int answer = 0;
        return answer = solve(words);
    }
}

문제 설명

캠핑

무지를 돌보느라 지친 콘은 한적한 시골의 한 캠핑장에 놀러 갔다. 캠핑장은 텐트를 칠 수 있는 넓은 평지를 제공하고 있는데, 이 평지에는 이미 캠핑장에서 설치해 놓은 n개의 쐐기가 박혀 있다. 캠핑장 이용 고객은 이 쐐기들 중 한 쌍을 골라 다음과 같은 조건을 만족하도록 텐트를 설치해야 한다.

• 텐트는 직사각형 형태여야 한다.
• 텐트의 네 면이 정확하게 동, 서, 남, 북을 향해야 한다.
• 대각에 위치하는 텐트의 두 꼭짓점이 정확하게 선택한 두 개의 쐐기에 위치해야 한다.
• 텐트가 점유하는 직사각형 영역의 넓이는 0보다는 커야 한다.
• 텐트가 점유하는 직사각형 영역 내부에 다른 쐐기를 포함하면 안 된다. (다른 쐐기가 경계에 위치하는 경우는 허용함)

캠핑장에서는 위와 같은 조건을 만족하는 위치라면 어디든 고객이 텐트를 설치할 수 있도록 정확한 크기의 텐트를 모두 구비하여 대여해준다고 한다.
당신은 위와 같은 조건을 만족하는 텐트를 설치할 수 있는 쐐기의 쌍의 개수는 총 몇 가지가 될지 궁금해졌다.
n개의 쐐기의 위치가 좌표로 주어질 때, 위의 조건을 만족하는 쐐기의 쌍의 개수를 계산하는 프로그램을 작성하시오. 단, 동서 방향은 x축, 남북 방향은 y축과 평행하다고 가정한다.

입력 형식

입력은 쐐기의 개수를 의미하는 정수 n과, n × 2 크기의 2차원 배열 data로 주어지며, 배열의 각 행은 캠핑장에 설치된 쐐기의 x좌표와 y좌표를 의미한다. 제한 조건은 다음과 같다.

• 2 <= n <= 5,000
• n개의 쐐기는 모두 x좌표 0 이상 2^31-1 이하, y좌표 0 이상 2^31-1 이하에 위치한다.
• 입력되는 n개의 쐐기 중 x좌표와 y좌표가 모두 같은 경우는 없다.

출력 형식

입력에 주어진 각 케이스에 대해 가능한 텐트의 쐐기의 쌍의 개수를 정수 형태로 리턴한다.

예제 입출력

ndataanswer

예제에 대한 설명

예제에는 총 4개의 쐐기가 있으며 이 중 (0,0)-(1,1), (0,2)-(1,1), (1,1)-(2,0)의 세 가지 위치에만 텐트를 설치할 수 있다. (0,0)-(0,2)와 (0,0)-(2,0)의 경우에는 직사각형 영역의 넓이가 0이 되기 때문에 조건을 만족하지 못하며, (0,2)-(2,0)의 경우 (1,1) 위치의 쐐기가 직사각형의 내부에 포함되므로 조건을 만족하지 못한다.

접근 방법

 문제 풀이의 핵심은 부분합과 좌표압축입니다. 문제를 처음보았을 때 부분합은 바로 떠올랐으나 문제에서 주어지는 좌표가 너무 커 어떻게 해결해야 하나 고민을 하였습니다. 

 이 때 좌표의 값과 상관없이 좌표의 크기 순서대로 좌표를 압축한다면 부분합을 사용하여 문제를 해결할 수 있습니다.

1. 좌표 압축

저와 같은 경우는 Hash Map을 사용하여 압축을 진행하였습니다.

(만약 데이터가 [100,121,999999999999]가 있다면 [0,1,2]로 변환가능)

1. map구조에 문제에서 주어진 좌표값들을 저장을 합니다.

2. map을 for문을 사용하여 데이터를 탐색하면 자동적으로 크기가 작은 값부터 탐색이 됩니다.(Hash 함수에 의해 value가 정렬되어 있음)

3. for문을 통해 탐색을 함과 동시에 value를 압축한 값으로 저장을 합니다.

void coordCompress(vector<vector<int>> &data){
    
    map<int, int> x_mapper;
    map<int, int> y_mapper;
    
    //1. 데이터를 hashmap에 저장(x와 y는 독립적임)
    for(int i=0;i<data.size();i++){
        int x = data[i][0];
        int y = data[i][1];
        if(x_mapper.count(x) == 0)
            x_mapper.insert({x, true});
        if(y_mapper.count(y) == 0)
            y_mapper.insert({y, true});
    }
    
    //좌표 압축을 진행
    int cnt = 0;
    for(auto &elem : x_mapper){ //2. 자동적으로 value가 작은 값부터 탐색됨
        int num = elem.first;
        x_mapper[num] = cnt++; //3. 좌표압축을 진행
    }
    cnt = 0;
    for(auto &elem : y_mapper){ //2. 자동적으로 value가 작은 값부터 탐색됨
        int num = elem.first;
        y_mapper[num] = cnt++; //3. 좌표압축을 진행
    }
    
    //변환된 좌표를 벡터에 저장하지 않고 map에서 계속해서 읽어오는 것은 속도저하를 유발하므로 
    //벡터로 저장을 해야함(map은 tree구조 이므로 데이터를 탐색하는 속도가 vector보다 느림)
    for(int i=0;i<data.size();i++){
        data[i][0] = x_mapper[data[i][0]];
        data[i][1] = y_mapper[data[i][1]];
    }
    M = x_mapper.size();
    N = y_mapper.size();
}

2. 부분합

 부분합을 사용하는 이유는 선택한 두 쐐기 사이에 포함되는 쐐기를 쉽게 식별할 수 있기 때문입니다. 

부분합 arr[x][y] = {0,0} ~ {x,y}사이에 있는 쐐기의 수를 의미합니다.

void make_arr(vector<vector<int>> &data){
    
    //압축된 좌표들의 정보로 arr에 좌표를 표시
    for(int i=0;i<data.size();i++){
        int x = data[i][0];
        int y = data[i][1];
        arr[x][y] = 1;
    }
    
    // arr[x][y] = {0,0} ~ {x,y}까지 존재하는 쐐기의 수 
    //태두리의 부분합을 구함
    for(int x = 1; x < M; x++)
        arr[x][0] += arr[x - 1][0];
    for(int y = 1; y < N; y++)
        arr[0][y] += arr[0][y - 1];
    
    //내부의 부분합을 구함
    for(int x = 1; x < M; x++){
        for(int y = 1; y < N; y++){
            arr[x][y] += arr[x - 1][y] + arr[x][y - 1] - arr[x - 1][y - 1];
        }    
    }
}

위의 과정 까지 진행했다면 2개의 쐐기를 선택하는 모든 경우에 대해 3가지 조건을 검사합니다.

1. 두 쐐기의 x좌표가 같은지

2. 두 쐐기의 y좌표가 같은지

3. 두 쐐기 사이에 다른 쐐기가 있는지(태두리에 쐐기가 있는 것은 무관함)

int solve(vector<vector<int>> &data){
    
    int cnt = 0;
    
    for(int i = 0; i < data.size(); i++){
        for(int j = i + 1; j < data.size(); j++){
            
            int h_x = max(data[i][0], data[j][0]);
            int h_y = max(data[i][1], data[j][1]);
            int l_x = min(data[i][0], data[j][0]);
            int l_y = min(data[i][1], data[j][1]);
            
            //x가 같거나, y가 같거나, 사이에 쐐기가 있는 경우
            if(h_x == l_x || h_y == l_y || 0 < arr[h_x - 1][h_y - 1] - arr[h_x - 1][l_y] - arr[l_x][h_y - 1] + arr[l_x][l_y])
                continue;  
            cnt++;
        }    
    }
    return cnt;
}

소스 코드

#include <vector>
#include <string.h>
#include <iostream>
#include <map>

using namespace std;

int arr[5001][5001];
int M, N;

void coordCompress(vector<vector<int>> &data){
    
    map<int, int> x_mapper;
    map<int, int> y_mapper;
    
    for(int i=0;i<data.size();i++){
        int x = data[i][0];
        int y = data[i][1];
        if(x_mapper.count(x) == 0)
            x_mapper.insert({x, true});
        if(y_mapper.count(y) == 0)
            y_mapper.insert({y, true});
    }
    
    int cnt = 0;
    for(auto &elem : x_mapper){
        int num = elem.first;
        x_mapper[num] = cnt++;
    }
    cnt = 0;
    for(auto &elem : y_mapper){
        int num = elem.first;
        y_mapper[num] = cnt++;
    }
    
    for(int i=0;i<data.size();i++){
        data[i][0] = x_mapper[data[i][0]];
        data[i][1] = y_mapper[data[i][1]];
    }
    M = x_mapper.size();
    N = y_mapper.size();
}

void make_arr(vector<vector<int>> &data){
    
    for(int i=0;i<data.size();i++){
        int x = data[i][0];
        int y = data[i][1];
        arr[x][y] = 1;
    }
    
    for(int x = 1; x < M; x++)
        arr[x][0] += arr[x - 1][0];
    for(int y = 1; y < N; y++)
        arr[0][y] += arr[0][y - 1];
    
    for(int x = 1; x < M; x++){
        for(int y = 1; y < N; y++){
            arr[x][y] += arr[x - 1][y] + arr[x][y - 1] - arr[x - 1][y - 1];
        }    
    }
}

int solve(vector<vector<int>> &data){
    
    int cnt = 0;
    
    for(int i = 0; i < data.size(); i++){
        for(int j = i + 1; j < data.size(); j++){
            
            int h_x = max(data[i][0], data[j][0]);
            int h_y = max(data[i][1], data[j][1]);
            int l_x = min(data[i][0], data[j][0]);
            int l_y = min(data[i][1], data[j][1]);
            
            //x가 같거나, y가 같거나, 사이에 쐐기가 있는 경우
            if(h_x == l_x || h_y == l_y || 0 < arr[h_x - 1][h_y - 1] - arr[h_x - 1][l_y] - arr[l_x][h_y - 1] + arr[l_x][l_y])
                continue;  
            cnt++;
        }    
    }
    return cnt;
}

// 전역 변수를 정의할 경우 함수 내에 초기화 코드를 꼭 작성해주세요.
int solution(int n, vector<vector<int>> data) {
    
    int answer = 0;
    memset(arr, 0, sizeof(arr));
    M = 0; N = 0;
    
    coordCompress(data);
    make_arr(data);
    
    answer = solve(data);
    return answer;
}

문제 설명

문제 설명

출발지점부터 distance만큼 떨어진 곳에 도착지점이 있습니다. 그리고 그사이에는 바위들이 놓여있습니다. 바위 중 몇 개를 제거하려고 합니다.
예를 들어, 도착지점이 25만큼 떨어져 있고, 바위가 [2, 14, 11, 21, 17] 지점에 놓여있을 때 바위 2개를 제거하면 출발지점, 도착지점, 바위 간의 거리가 아래와 같습니다.

제거한 바위의 위치각 바위 사이의 거리거리의 최솟값

위에서 구한 거리의 최솟값 중에 가장 큰 값은 4입니다.

출발지점부터 도착지점까지의 거리 distance, 바위들이 있는 위치를 담은 배열 rocks, 제거할 바위의 수 n이 매개변수로 주어질 때, 바위를 n개 제거한 뒤 각 지점 사이의 거리의 최솟값 중에 가장 큰 값을 return 하도록 solution 함수를 작성해주세요.

제한사항

• 도착지점까지의 거리 distance는 1 이상 1,000,000,000 이하입니다.
• 바위는 1개 이상 50,000개 이하가 있습니다.
• n 은 1 이상 바위의 개수 이하입니다.

입출력 예

distancerocksnreturn

접근 방법

 꽤 난이도가 있는 이분탐색 문제였습니다.

1. 문제 풀이의 핵심은 mid를 "거리의 최소값"으로 생각하고 징검다리를 순차적으로 최대 n개까지 제거해보며 모두 간격이 mid보다 넓은지 확인하는 것이다. 

2-1. 만약 mid보다 좁은 간격이라면 다음 징검다리를 제거하고 다음 징검다리까지의 간격을 확인합니다. (최대 n번까지 가능)

2-2. 만약 n개의 징검다리를 제거 했음에도 mid보다 좁은 간격의 징검다리가 존재한다면 mid는 만족할 수 없음으로 mid를 줄여 조정합니다. 

3. 만약 mid와 같거나 넓은 간격이라면 mid를 증가시켜보며 mid의 최댓값을 구합니다.

소스 코드

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

vector<int> diffs; //간격을 저장한 벡터

void init(vector<int> &rocks, int dist){
    
    sort(rocks.begin(), rocks.end());
    
    int start = 0;
    for(int i=0;i<rocks.size();i++){
        int diff = rocks[i] - start;
        diffs.push_back(diff);
        start = rocks[i];
    }
    diffs.push_back(dist - rocks.back());
}

int bSearch(int distance, int n){
    
    int start = 1;
    int end = distance;
    int result = 0;
    
    while(start <= end){
        
        int mid = (start + end) / 2;
        int removeCnt = 0; //제거한 징검다리의 수
        int prevDist = 0; //징검다리를 제거하였을 때 연장되는 길이를 저장한 값
        
        //모든 간격이 mid보다 넓은지 확인하는 과정
        for(int i=0;i<diffs.size();i++){
            if(mid > diffs[i] + prevDist){ //징검다리를 제거해야 하는 경우
                prevDist += diffs[i];
                removeCnt++;
            }
            else{ //징검다리를 제거하지 않고 만족하는 경우
                prevDist = 0;
            }
            if(removeCnt > n)
                break;
        }
        
        if(removeCnt > n){
            end = mid - 1;
        }
        else{
            result = (result == 0) ? mid : max(mid, result);
            start = mid + 1;
        }
    }
    return result;
}

int solution(int distance, vector<int> rocks, int n) {
    
    int answer = 0;
    init(rocks, distance);
    
    return answer = bSearch(distance, n);
}

문제 설명

문제 설명

n명이 입국심사를 위해 줄을 서서 기다리고 있습니다. 각 입국심사대에 있는 심사관마다 심사하는데 걸리는 시간은 다릅니다.

처음에 모든 심사대는 비어있습니다. 한 심사대에서는 동시에 한 명만 심사를 할 수 있습니다. 가장 앞에 서 있는 사람은 비어 있는 심사대로 가서 심사를 받을 수 있습니다. 하지만 더 빨리 끝나는 심사대가 있으면 기다렸다가 그곳으로 가서 심사를 받을 수도 있습니다.

모든 사람이 심사를 받는데 걸리는 시간을 최소로 하고 싶습니다.

입국심사를 기다리는 사람 수 n, 각 심사관이 한 명을 심사하는데 걸리는 시간이 담긴 배열 times가 매개변수로 주어질 때, 모든 사람이 심사를 받는데 걸리는 시간의 최솟값을 return 하도록 solution 함수를 작성해주세요.

제한사항

• 입국심사를 기다리는 사람은 1명 이상 1,000,000,000명 이하입니다.
• 각 심사관이 한 명을 심사하는데 걸리는 시간은 1분 이상 1,000,000,000분 이하입니다.
• 심사관은 1명 이상 100,000명 이하입니다.

입출력 예

ntimesreturn

입출력 예 설명

가장 첫 두 사람은 바로 심사를 받으러 갑니다.

7분이 되었을 때, 첫 번째 심사대가 비고 3번째 사람이 심사를 받습니다.

10분이 되었을 때, 두 번째 심사대가 비고 4번째 사람이 심사를 받습니다.

14분이 되었을 때, 첫 번째 심사대가 비고 5번째 사람이 심사를 받습니다.

20분이 되었을 때, 두 번째 심사대가 비지만 6번째 사람이 그곳에서 심사를 받지 않고 1분을 더 기다린 후에 첫 번째 심사대에서 심사를 받으면 28분에 모든 사람의 심사가 끝납니다.

접근 방법

 이분탐색을 활용하여 풀 수 있는 재미있는 문제였습니다.

이분탐색에서의 mid를 모든 사람을 심사하는데 걸리는 시간으로 잡고 최소가 되는 mid를 구하면 됩니다. 

 mid초 일 때 심사 할 수 있는 인원을 계산하는 방법은 각 인원(times[i])이 mid초 동안 몇 명을 심사할 수 있는지 계산하여 합하면 구할 수 있습니다. (심사한 인원 = times[i] / mid )

 이 때 mid초 동안 총 심사한 인원이 cnt명이라 할 때 cnt < n이면 더욱 많은 시간이 소요된다는 의미이고, 그 반대의 경우는 mid초 동안 n명을 모두 심사할 수 있다는 의미가 됩니다. 

즉 cnt >= n인 경우를 만족하는 mid중 최솟 값이 정답이 됩니다.

소스 코드

#include <string>
#include <vector>
#include <algorithm>
#include <iostream>

using namespace std;

vector<long long> v;

long long bSearch(int n, vector<int> &times){
    
    sort(times.begin(), times.end());
    
    long long start = 1;
    long long end = times.back() * (long long)n;
    long long result = 0;
    
    while(start <= end){
        
        long long mid = (start + end)/2;
        
        long long cnt = 0;
        for(int i=0;i<times.size();i++){
            cnt += mid / times[i]; //mid시간 동안 처리할 수 있는 사람의 수 
        }
        
        if(cnt < n){ //시간내로 처리 불가능, 처리시간 증가 요구
            start = mid + 1;
        }
        else{
            result = (result == 0) ? mid : min(result, mid);
            end = mid - 1;
        }
    }
    return result;
}

long long solution(int n, vector<int> times) {
    long long answer = 0;
    return answer = bSearch(n, times); 
}

문제 설명

셔틀버스

카카오에서는 무료 셔틀버스를 운행하기 때문에 판교역에서 편하게 사무실로 올 수 있다. 카카오의 직원은 서로를 '크루'라고 부르는데, 아침마다 많은 크루들이 이 셔틀을 이용하여 출근한다.

이 문제에서는 편의를 위해 셔틀은 다음과 같은 규칙으로 운행한다고 가정하자.

• 셔틀은 09:00부터 총 n회 t분 간격으로 역에 도착하며, 하나의 셔틀에는 최대 m명의 승객이 탈 수 있다.
• 셔틀은 도착했을 때 도착한 순간에 대기열에 선 크루까지 포함해서 대기 순서대로 태우고 바로 출발한다. 예를 들어 09:00에 도착한 셔틀은 자리가 있다면 09:00에 줄을 선 크루도 탈 수 있다.

일찍 나와서 셔틀을 기다리는 것이 귀찮았던 콘은, 일주일간의 집요한 관찰 끝에 어떤 크루가 몇 시에 셔틀 대기열에 도착하는지 알아냈다. 콘이 셔틀을 타고 사무실로 갈 수 있는 도착 시각 중 제일 늦은 시각을 구하여라.

단, 콘은 게으르기 때문에 같은 시각에 도착한 크루 중 대기열에서 제일 뒤에 선다. 또한, 모든 크루는 잠을 자야 하므로 23:59에 집에 돌아간다. 따라서 어떤 크루도 다음날 셔틀을 타는 일은 없다.

입력 형식

셔틀 운행 횟수 n, 셔틀 운행 간격 t, 한 셔틀에 탈 수 있는 최대 크루 수 m, 크루가 대기열에 도착하는 시각을 모은 배열 timetable이 입력으로 주어진다.

• 0 ＜ n ≦ 10
• 0 ＜ t ≦ 60
• 0 ＜ m ≦ 45
• timetable은 최소 길이 1이고 최대 길이 2000인 배열로, 하루 동안 크루가 대기열에 도착하는 시각이 HH:MM 형식으로 이루어져 있다.
• 크루의 도착 시각 HH:MM은 00:01에서 23:59 사이이다.

출력 형식

콘이 무사히 셔틀을 타고 사무실로 갈 수 있는 제일 늦은 도착 시각을 출력한다. 도착 시각은 HH:MM 형식이며, 00:00에서 23:59 사이의 값이 될 수 있다.

입출력 예제

ntmtimetableanswer

접근 방법

가장 마지막에 타기 위해서는 가장 마지막 버스를 타면 됩니다. 이 때 2가지 경우가 있습니다.

1. 마지막 버스에 빈자리가 있는 경우

2. 마지막 버스에 빈자리가 없는 경우

1번의 경우 마지막 버스의 출발시간이 정답이 될 것입니다.

2번의 경우는 마지막 버스에 마지막으로 올라탄 사람보다 1분 일찍 도착한다면 마지막 버스를 탈 수 있게 될 것입니다.

문제 풀이

1. 위의 결과를 도출하기 위해 [버스에 타고있는 인원, 버스의 출발시간, 버스에 마지막으로 탄 사람의 도착시간] 3가지의 정보가 필요합니다. 이 3가지의 정보를 담고 있는 구조체를 가진 배열을 초기화 합니다.

2. 또한 timetable이 string의 형식이므로 계산을 편히 하기 위해 int로 바꾸어줄 필요가 있습니다. int형으로 바꾸어 주었다면 사람들을 도착한 순서대로 정렬을 시킵니다.  

typedef struct info{
    int cnt, start, last;
};

vector<int> table; //timetable을 int로 변환
vector<info> busTable; //버스 배열

void init(vector<string> &timetable, int n, int t, int m){
    
    //time table을 int로 변환하여 table에 입력
    for(int i=0;i<timetable.size();i++){
        string t = timetable[i];
        int h = atoi(t.substr(0,2).c_str()); 
        int m = atoi(t.substr(3,2).c_str()); 
        table.push_back(h*60 + m);
    }
    //도착한 순서대로 정렬(오름차순)
    sort(table.begin(), table.end());
    
    //버스의 정보를 담고 있는 배열 초기화
    int start = 9*60; //출발시간이 09:00이므로
    for(int i=0;i<n;i++){ //버스는 n번 운행 됨
        busTable.push_back({0, start, 0}); //탑승한 인원, 출발시간, 마지막에 탑승한 사람의 도착시간 
        start += t; //t분 간격으로 운행
    }
}

이러한 초기화 과정의 끝났다면 모든 승객을 버스에 배치 시켜 봅니다.

 사람의 도착시간이 버스의 출발시간 보다 빠르고 버스에 빈 자리가 있을 때에만 버스에 탑승이 가능합니다.

반대의 경우는 탑승 불가능 하며 다음 버스에 배치를 해야합니다.

string solve(int m, int n){
    
    int busNum = 0;
    string ans = "";
    
    for(int i=0;i<table.size();i++){
        //버스에 탈 수 있는 경우, 수용가능하며 시간이 맞을 때
        if(busTable[busNum].cnt < m && table[i] <= busTable[busNum].start){
            busTable[busNum].cnt++;
            busTable[busNum].last = table[i];
        } // 시간이 밀리거나 버스가 꽉 찾다면
        else{
            busNum++; //다음 버스
            i--;  //현재 인원이 아직 처리가 안됬기 때문임
        }
        
        //모든 버스가 운행 종료
        if(busNum >= n)
            break;
    }
    
    //마지막 버스
    info bus = busTable.back();
    //버스에 빈 자리가 있다면 버스의 출발시간, 아니라면 버스에 탑승한 마지막 인원 보다 1분 일찍
    return ans = (bus.cnt < m) ? intToStr(bus.start) : intToStr(bus.last - 1);
}

소스 코드

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

typedef struct info{
    int cnt, start, last;
};

vector<int> table;
vector<info> busTable;

void init(vector<string> &timetable, int n, int t, int m){
    
    for(int i=0;i<timetable.size();i++){
        string t = timetable[i];
        int h = atoi(t.substr(0,2).c_str());
        int m = atoi(t.substr(3,2).c_str());
        table.push_back(h*60 + m);
    }
    sort(table.begin(), table.end());
    
    int start = 9*60;
    for(int i=0;i<n;i++){
        busTable.push_back({0, start, 0});
        start += t;
    }
}

string intToStr(int time){
    
    int h = time/60;
    int m = time%60;
    
    string H = to_string(h);
    string M = to_string(m);
    
    H = (H.size() == 1) ? "0" + H : H;
    M = (M.size() == 1) ? "0" + M : M;
    
    return H + ":" + M;
}

string solve(int m, int n){
    
    int busNum = 0;
    string ans = "";
    
    for(int i=0;i<table.size();i++){
        //버스에 탈 수 있는 경우, 수용가능하며 시간이 맞을 때
        if(busTable[busNum].cnt < m && table[i] <= busTable[busNum].start){
            busTable[busNum].cnt++;
            busTable[busNum].last = table[i];
        } // 시간이 밀리거나 버스가 꽉 찾다면
        else{
            busNum++;
            i--;
        }
        
        if(busNum >= n)
            break;
    }
    
    info bus = busTable.back();
    return ans = (bus.cnt < m) ? intToStr(bus.start) : intToStr(bus.last - 1);
}

string solution(int n, int t, int m, vector<string> timetable) {
    string answer = "";
    init(timetable,n,t,m);
    
    return answer = solve(m, n);
}

문제 설명

보행자 천국

카카오내비 개발자인 제이지는 시내 중심가의 경로 탐색 알고리즘 개발 업무를 담당하고 있다. 최근 들어 보행자가 자유롭고 편리하게 걸을 수 있도록 보행자 중심의 교통 체계가 도입되면서 도심의 일부 구역은 자동차 통행이 금지되고, 일부 교차로에서는 보행자 안전을 위해 좌회전이나 우회전이 금지되기도 했다. 복잡해진 도로 환경으로 인해 기존의 경로 탐색 알고리즘을 보완해야 할 필요가 생겼다.

도시 중심가의 지도는 m × n 크기의 격자 모양 배열 city_map으로 주어진다. 자동차는 오른쪽 또는 아래 방향으로 한 칸씩 이동 가능하다.

city_map[i][j]에는 도로의 상황을 나타내는 값이 저장되어 있다.

• 0인 경우에는 자동차가 자유롭게 지나갈 수 있다.
• 1인 경우에는 자동차 통행이 금지되어 지나갈 수 없다.
• 2인 경우는 보행자 안전을 위해 좌회전이나 우회전이 금지된다. (왼쪽에서 오던 차는 오른쪽으로만, 위에서 오던 차는 아래쪽으로만 진행 가능하다)

도시의 도로 상태가 입력으로 주어졌을 때, 왼쪽 위의 출발점에서 오른쪽 아래 도착점까지 자동차로 이동 가능한 전체 가능한 경로 수를 출력하는 프로그램을 작성하라. 이때 가능한 경로의 수는 컴퓨터가 표현할 수 있는 정수의 범위를 넘어설 수 있으므로, 가능한 경로 수를 20170805로 나눈 나머지 값을 출력하라.

입력 형식

입력은 도시의 크기를 나타내는 m과 n, 그리고 지도를 나타내는 2차원 배열 city_map으로 주어진다. 제한조건은 아래와 같다.

• 1 <= m, n <= 500
• city_map의 크기는 m × n이다.
• 배열의 모든 원소의 값은 0, 1, 2 중 하나이다.
• 출발점의 좌표는 (0, 0), 도착점의 좌표는 (m - 1, n - 1)이다.
• 출발점과 도착점의 city_map[i][j] 값은 0이다.

출력 형식

출발점에서 도착점까지 이동 가능한 전체 경로의 수를 20170805로 나눈 나머지를 리턴한다.

예제 입출력

mncity_mapanswer

예제에 대한 설명

첫 번째 예제는 모든 도로가 제한 없이 통행 가능한 경우로, 가능한 경우의 수는 6가지이다.
두 번째 예제는 문제 설명에 있는 그림의 경우이다. 가능한 경우의 수는 빨간 실선과 노란 점선 2가지뿐이다.

접근 방법

 동적계획법으로 해결할 수 있는 문제였습니다. 동적계획법은 dp[x좌표][y좌표][현재방향]으로 설계할 수 있으며 현재방향에 대한 차원이 필요한 이유는 만약 어떤 지점의 값이 2일때 한 방향으로만 갈 수 있으므로 현재 어떤 방향을 가지고 있는가에 따라 다른 경우의 수가 되기 때문입니다. 

 자세한 내용은 코드에 주석을 달아놓겠습니다.

소스 코드

#include <vector>
#include <string.h>

using namespace std;

int MOD = 20170805;
int dp[501][501][2]; //마지막 차원은 현재 방향
pair<int, int> nextdir[2] = {{1,0},{0,1}}; //오른쪽 또는 아래로만 이동 가능
vector<vector<int>> map;
int M, N;

bool inRange(int x, int y){
    return (0 <= x && x < M && 0 <= y && y < N);
}

int solve(int x, int y, int dir){
    
    int &ref = dp[x][y][dir];
    
    //방문한 적 있다면
    if(ref != -1)
        return ref;
    //목표지점에 도달했다면
    if(x == M - 1 && y == N - 1)
        return ref = 1;
    
    //방문 표시
    ref = 0;
    //2방향 모두 가능
    if(map[x][y] != 2){
        
        //2방향에 대한 반복문
        for(int i=0;i<2;i++){
            int next_x = x + nextdir[i].first;
            int next_y = y + nextdir[i].second;
            //다음 좌표가 범위를 벗어나지 않으며 통행 불가 지역이 아닌 경우
            if(inRange(next_x, next_y) && map[next_x][next_y] != 1)
                ref += solve(next_x, next_y, i) % MOD;     
        }    
    }
    else{ //회전 불가능, map[x][y] == 2인 경우
        //현재 진행 방향이 dir이며 dir로만 진행 가능
        int next_x = x + nextdir[dir].first;
        int next_y = y + nextdir[dir].second;
        if(inRange(next_x, next_y) && map[next_x][next_y] != 1)
            ref += solve(next_x, next_y, dir) % MOD;     
    }
    return ref %= MOD;
}

// 전역 변수를 정의할 경우 함수 내에 초기화 코드를 꼭 작성해주세요.
int solution(int m, int n, vector<vector<int>> city_map) {
    
    int answer = 0;
    memset(dp, -1, sizeof(dp));
    //전역 변수로 초기화
    M = m; N = n; map = city_map;
    
    return answer = solve(0, 0, 0);
}

문제 설명

N x N 크기인 정사각 격자 형태의 지형이 있습니다. 각 격자 칸은 1 x 1 크기이며, 숫자가 하나씩 적혀있습니다. 격자 칸에 적힌 숫자는 그 칸의 높이를 나타냅니다.

이 지형의 아무 칸에서나 출발해 모든 칸을 방문하는 탐험을 떠나려 합니다. 칸을 이동할 때는 상, 하, 좌, 우로 한 칸씩 이동할 수 있는데, 현재 칸과 이동하려는 칸의 높이 차가 height 이하여야 합니다. 높이 차가 height 보다 많이 나는 경우에는 사다리를 설치해서 이동할 수 있습니다. 이때, 사다리를 설치하는데 두 격자 칸의 높이차만큼 비용이 듭니다. 따라서, 최대한 적은 비용이 들도록 사다리를 설치해서 모든 칸으로 이동 가능하도록 해야 합니다. 설치할 수 있는 사다리 개수에 제한은 없으며, 설치한 사다리는 철거하지 않습니다.

각 격자칸의 높이가 담긴 2차원 배열 land와 이동 가능한 최대 높이차 height가 매개변수로 주어질 때, 모든 칸을 방문하기 위해 필요한 사다리 설치 비용의 최솟값을 return 하도록 solution 함수를 완성해주세요.

제한사항

• land는 N x N크기인 2차원 배열입니다.
• land의 최소 크기는 4 x 4, 최대 크기는 300 x 300입니다.
• land의 원소는 각 격자 칸의 높이를 나타냅니다.
• 격자 칸의 높이는 1 이상 10,000 이하인 자연수입니다.
• height는 1 이상 10,000 이하인 자연수입니다.

입출력 예

landheightresult

입출력 예 설명

입출력 예 #1

각 칸의 높이는 다음과 같으며, 높이차가 3 이하인 경우 사다리 없이 이동이 가능합니다.

위 그림에서 사다리를 이용하지 않고 이동 가능한 범위는 같은 색으로 칠해져 있습니다. 예를 들어 (1행 2열) 높이 4인 칸에서 (1행 3열) 높이 8인 칸으로 직접 이동할 수는 없지만, 높이가 5인 칸을 이용하면 사다리를 사용하지 않고 이동할 수 있습니다.

따라서 다음과 같이 사다리 두 개만 설치하면 모든 칸을 방문할 수 있고 최소 비용은 15가 됩니다.

• 높이 5인 칸 → 높이 10인 칸 : 비용 5
• 높이 10인 칸 → 높이 20인 칸 : 비용 10

입출력 예 #2

각 칸의 높이는 다음과 같으며, 높이차가 1 이하인 경우 사다리 없이 이동이 가능합니다.

위 그림과 같이 (2행 1열) → (1행 1열), (1행 2열) → (2행 2열) 두 곳에 사다리를 설치하면 설치비용이 18로 최소가 됩니다.

접근 방법

 최소 신장 트리 알고리즘을 알고 있다면 크게 생각할 부분이 없는 문제였습니다. 

 최소 신장 트리는 모든 노드를 연결하였을 때 드는 간선의 최소 비용을 구하는 알고리즘입니다. 그러므로 문제에서 모든 칸을 이동할 수 있도록 사다리를 설치해야 한다는 점과 사다리의 설치 비용의 최소가 된다는 점을 본다면 MST(최소 신장 트리)를 바로 떠올릴 수 있습니다. 

사다리 설치가 없는 지역간의 이동 비용은 0, 사다리를 설치해야하는 지역간의 이동 비용은 인접한 격자 값의 차이가 될 것입니다. 

유의할 점으로 최소 신장 트리를 구성할 때 노드 번호를 격자의 좌표인 2차원 좌표로 표현하였습니다.

소스 코드

#include <string>
#include <vector>
#include <cmath>
#include <algorithm>

using namespace std;

typedef struct coord{
    int x, y;
};
typedef struct info{
    coord now, next;
    int cost;
};

vector<info> costmap;
pair<int, int> nextdir[2] = {{1,0},{0,1}};
coord parent[301][301];

bool comp(info &a, info &b){
    return a.cost < b.cost;
}

void make_costmap(vector<vector<int>> &land, int h){
    
    for (int i = 0; i < land.size(); i++) 
        for (int j = 0; j < land.size(); j++) 
            parent[i][j] = {i,j};    
    
    for(int i=0;i<land.size();i++){
        for(int j=0;j<land.size();j++){
            for(int dir=0;dir<2;dir++){
                int next_x = i + nextdir[dir].first;
                int next_y = j + nextdir[dir].second;
                if(0 <= next_x && next_x < land.size() && 0 <= next_y && next_y < land.size()){
                    if(abs(land[i][j] - land[next_x][next_y]) <= h) costmap.push_back({{i,j},{next_x, next_y}, 0});
                    else costmap.push_back({{i,j},{next_x, next_y}, abs(land[i][j] - land[next_x][next_y])});
                }
            }
        }    
    }
}

coord find(coord a) {
	if (parent[a.x][a.y].x == a.x && parent[a.x][a.y].y == a.y) {
		return a;
	}
	coord root = find(parent[a.x][a.y]);
	return root;
}

bool Union(coord a, coord b) {
	a = find(a);
	b = find(b);
	if (a.x != b.x || a.y != b.y) {
		parent[b.x][b.y] = a;
		return true;
	}
	return false;
}

int solve(){
    
    sort(costmap.begin(), costmap.end(), comp);
    
    int result = 0;
	for (int i = 0; i < costmap.size(); i++) {
		if (Union(costmap[i].now, costmap[i].next)) 
			result += costmap[i].cost;
	}
    return result;
}

int solution(vector<vector<int>> land, int height) {
    int answer = 0;
    make_costmap(land, height);
    return answer = solve();
}