(프로그래머스) 지형 이동

문제

https://programmers.co.kr/learn/courses/30/lessons/62050

접근

BFS vs DFS

제약사항 중 입력 최대 크기가 300 * 300 = 90000이다. DFS로는 재귀의 깊이가 너무 깊어질 것으로 예상되어 BFS로 풀게 되었다.

사다리는 어디에?

처음에는 단순히 순서대로 탐색하며 영역을 나누면서 사다리를 설치할 위치를 정하면 된다고 생각하고 구현했는데, 다 구현하자마자 반례가 떠올랐다.

영역마다 다른 색을 칠하였으며 빨간 색으로 표시한 곳이 사다리를 놓은 위치다. 하지만 기존 방법처럼 영역을 나누는 과정에서 사다리를 놓을 위치를 구하게 된다면 후자와 같은 경우 오답을 구하게 된다.
(좌측에서 우측으로, 위에서 아래로 순서대로 탐색하며 구하기 때문이다.)

이렇게 된 이상, 사다리를 놓을 수 있는 경우에 대해서 우선 구해놓아야 한다는 결론을 내리게 되었다. 그렇다면 배치는 어떻게 해야 할지 고민할 차례이다.

여기서 중요한건, 모든 영역을 연결하기 위해서는,
사다리가 최소한 영역의 개수 - 1 개가 필요하다.

여기서 Union-Find 방식으로 구하면 되겠다는 힌트를 얻고 구현하게 되었다.

코드

import java.util.*;

class Node {
    int x;
    int y ;
    
    Node(int x, int y) {
        this.x = x;
        this.y = y;
    }
}

class AnsNode implements Comparable<AnsNode>{
    int n1;
    int n2; 
    int value;
    
    AnsNode (int n1, int n2, int value) {
        this.n1 = n1;
        this.n2 = n2;
        this.value = value;
    }
    
    @Override
    public int compareTo(AnsNode a) {
        if (this.value > a.value) {
            return 1;
        }
        
        return -1;
    }
}

class Solution {
    
    int[] group; // 연결 여부 확인용
    public int solution(int[][] land, int height) {
        int answer = 0;
        int len = land.length;
        
        boolean[][] visited = new boolean[len][len];
        int[][] map = new int[len][len];
        int num = 1; // 영역 번호
        
        int[] dx = {0, 0, -1, 1};
        int[] dy = {-1, 1, 0, 0};
        
        PriorityQueue<AnsNode> pq = new PriorityQueue<>();
        
        for (int i = 0; i < len; i++) {
            for (int j = 0; j < len; j++) {
                if (!visited[i][j]) {
                    Queue<Node> q = new LinkedList<>();
                    q.add(new Node(j, i));
                    visited[i][j] = true;
                    map[i][j] = num;
                                        
                    while (!q.isEmpty()) {
                        Node node = q.remove();
                        int x = node.x;
                        int y = node.y;
                        
                        for (int k = 0; k < 4; k++) {
                            int nextX = x + dx[k];
                            int nextY = y + dy[k];
                            
                            if (nextX < 0 || len <= nextX || nextY < 0 || len <= nextY) {
                                continue;
                            }
                            
                            // 다음 지점이 방문 안한 점일 때
                            if (!visited[nextY][nextX]) {
                                if (Math.abs(land[y][x] - land[nextY][nextX]) <= height) {
                                    q.add(new Node(nextX, nextY));
                                    visited[nextY][nextX] = true;
                                    map[nextY][nextX] = num;
                                } 
                            } 
                            
                            // 다음 지점이 방문한 점일 때
                            else {
                                if (map[nextY][nextX] == num) {
                                    continue;
                                }
                                
                                int n1 = num;
                                int n2 = map[nextY][nextX];
                                int value = Math.abs(land[y][x] - land[nextY][nextX]);
                                
                                pq.add(new AnsNode(n1, n2, value));
                            }
                        }
                    }
                    
                    num++;
                }
            }
        }        
        
        // 그룹 배열 초기화
        group = new int[num];
        for (int i = 0; i < num; i++) {
            group[i] = i;
        }
        
        int ansCnt = 0;
        while (!pq.isEmpty()) {
            if (ansCnt == num) {
                break;
            }
            
            AnsNode ansNode = pq.remove();
            int n1 = ansNode.n1;
            int n2 = ansNode.n2;
            int value = ansNode.value;
            
            // 같은 그룹이면 연결할 필요 없음.
            if (find(n1) == find(n2)) {
                continue;
            }
            
            union(n1, n2);
            answer += value;
        }
        
        return answer;
    }
    
    void union(int a, int b) {
        int ap = find(a);
        int bp = find(b);
        
        group[ap] = bp;
    }
    
    int find(int n) {
        if (group[n] == n) {
            return group[n];
        }
        
        group[n] = find(group[n]);
        return group[n];
    }
}

처음에 놓쳤던 부분들

• 방문된 영역 탐색 시 본인 영역인지 다른 영역인지 확인 필요
• 사다리를 놓을 부분을 영역 나누면서가 아닌, 영역을 전부 나눈 후 구해야 한다.