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

package level4;
import java.util.*;
public class Solution_지형이동 {
	static class Pos{
        int x,y;
        Pos(int x, int y){
            this.x = x;
            this.y = y;
        }
    }
    
    static class Edge{
        Pos a,b;
        int value;
        Edge(Pos a, Pos b, int value){
            this.a = a;
            this.b = b;
            this.value = value;
        }
    }
    
    static boolean check(int x, int y, int[][] map){
        if(x>=0 && y>=0 && x<map.length && y<map[x].length){
            return true;
        }else return false;
    }
	static int[][] dir = { { 0, 1 }, { 1, 0 }, { 0, -1 }, { -1, 0 } };
    static public int solution(int[][] land, int height) {
        int answer = 0;
        int[][] group = new int[land.length][land[0].length];
        Queue<Pos> qu = new LinkedList<>();
        int dx,dy;
        int index = 0;
        Queue<Edge> pq = new PriorityQueue<>(new Comparator<Edge>(){
            @Override
            public int compare(Edge o1, Edge o2){
                return o1.value - o2.value;
            }
        });
        
        for(int i=0; i<land.length; i++){
            for(int j=0; j<land[i].length; j++){
                if(group[i][j] == 0){
                    index ++;
                    group[i][j] = index;
                    qu.add(new Pos(i,j));
                    while(!qu.isEmpty()){
                        Pos p = qu.poll();
                        for(int d=0; d<4; d++){
                            dx = p.x + dir[d][0];
                            dy = p.y + dir[d][1];
                            if(check(dx, dy, land) && group[dx][dy] == 0){
                                Pos np = new Pos(dx,dy);
                                int diff = Math.abs(land[p.x][p.y]-land[dx][dy]);
                                if(diff <= height){
                                    group[dx][dy] = index;
                                    qu.add(new Pos(dx,dy));
                                }else{
                                    pq.add(new Edge(p, np, diff));
                                }
                            }
                        }
                    }
                }
            }
        }
		parent = new int[index + 1];
		for (int i = 1; i < parent.length; i++) {
			parent[i] = i;
		}
		while (!pq.isEmpty()) {
			Edge e = pq.poll();
			int a = group[e.a.x][e.a.y];
			int b = group[e.b.x][e.b.y];
			if (union(a, b))
				answer += e.value;
		}
		return answer;
	}
	static int[] parent;
	static int find(int x) {
		if (parent[x] == x)
			return x;
		return parent[x] = find(parent[x]);
	}
	static boolean union(int a, int b) {
		int ap = find(a);
		int bp = find(b);
		if (ap < bp) {
			parent[bp] = ap;
			return true;
		}else if(ap > bp){
			parent[ap] = bp;
			return true;
		}else return false;
	}
}