[프로그래머스] 지형 이동

문제

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

코딩테스트 연습 - 지형 이동

문제해결방법

1. 처음에 land 배열을 돌면서 사다리 없이 이동할 수 있는 격자들끼리 그룹을 지어주었다.

2. Union-Find 작업을 해주기 위해 그룹의 개수만큼 Parent 배열을 만들어주었다.

3. 다시 land 배열을 돌면서 각 격자마다 상,하,좌,우를 확인하며 그룹이 다르면 사다리를 놓을 수 있는 경우를 우선순위 큐에 넣는다. (사다리 설치 비용이 작은 순으로 정렬된 우선순위 큐 / {사다리 설치 비용, 현재 격자, 비교 격자} )

4. 우선순위 큐에서 하나씩 꺼내며 두 격자의 Parent가 다르면 Union 작업을 해준다.
   (이 작업이 발생할 때마다 사다리 설치 비용을 더해준다.)

코드

package Programmers;
 
import java.util.ArrayDeque;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Queue;
 
public class Solution_지형이동 {
 
    public static int[][] dir = {{0, -1}, {-1, 0}, {0, 1}, {1, 0}};
    
    public static void bfs(int i, int j, int height, int N, int[][] map, int[][] group, int groupNum) {
        Queue<int[]> q = new ArrayDeque<int[]>();
        q.add(new int[] {i, j});
        group[i][j] = groupNum;
        while(!q.isEmpty()) {
            int[] cur = q.poll();
            int h = map[cur[0]][cur[1]];
            for(int d=0; d<dir.length; d++) {
                int xx = cur[0] + dir[d][0];
                int yy = cur[1] + dir[d][1];
                if(xx>=0 && xx<N && yy>=0 && yy<N && group[xx][yy]==0 && Math.abs(h-map[xx][yy])<=height) {
                    group[xx][yy] = groupNum;
                    q.add(new int[] {xx, yy});
                }
            }
        }
    }
    
    public static void init(int[] parent) {
        for(int i=1; i<parent.length; i++) parent[i] = i;
    }
    
    public static int find(int node, int[] parent) {
        if(parent[node]==node) return node;
        return parent[node] = find(parent[node], parent);
    }
    
    public static void union(int a, int b, int[] parent) {
        int pa = find(a, parent);
        int pb = find(b, parent);
        parent[pa] = pb;
    }
    
    public static int solution(int[][] land, int height) {
        int answer = 0;
        int N = land.length;
        int [][] group = new int[N][N];
        int g = 1;
        for(int i=0; i<N; i++) {
            for(int j=0; j<N; j++) {
                if(group[i][j]==0)
                    bfs(i, j, height, N, land, group, g++);
            }
        }
 
        int[] parent = new int[g];
        init(parent);
        PriorityQueue<int[]> pq = new PriorityQueue<int[]>(new Comparator<int[]>() {
            @Override
            public int compare(int[] arg0, int[] arg1) {
                return Integer.compare(arg0[0], arg1[0]);
            }
        });
        
        for(int i=0; i<N; i++) {
            for(int j=0; j<N; j++) {
                int groupNum = group[i][j];
                int h = land[i][j];
                for(int d=0; d<2; d++) {
                    int xx = i + dir[d][0];
                    int yy = j + dir[d][1];
                    if(xx>=0 && xx<N && yy>=0 && yy<N && groupNum!=group[xx][yy]) {
                        pq.add(new int[] {Math.abs(h-land[xx][yy]), groupNum, group[xx][yy]});
                    }
                }
            }
        }
        
        while(!pq.isEmpty()) {
            int[] edge = pq.poll();
            if(find(edge[1], parent)!=find(edge[2], parent)) {
                answer += edge[0];
                union(edge[1], edge[2], parent);
                g--;
                if(g<=2) break;
            }
        }
        
        return answer;
    }
    
    public static void main(String[] args) {
        int[][] land = {{10, 11, 10, 11}, {2, 21, 20, 10}, {1, 20, 21, 11}, {2, 1, 2, 1}};
        int height = 1;
        System.out.println(solution(land, height));
    }
}

코드에 대한 피드백이나 더 좋은 아이디어는 언제나 환영입니다.