프로그래머스 ) 지형이동

 

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

프로그래머스

---

 

특정높이 이하로 움직일 수있는 공간에 mark를 남겨주고

이 mark만큼 크루스칼알고리즘을 적용하여

간선의 최솟값만큼만 노드들을 연결할 수 있게 해준다.

 

사실 pq에 1->2 가는 노드와 2->1 가는 노드가 같은것인데 들어있어서 비효율적일것같다.

---

import java.util.ArrayDeque;
import java.util.Comparator;
import java.util.PriorityQueue;

class Solution {
    public static int parent[];
	public static int find(int x) {
		if(parent[x] ==x) return x;
		else return find(parent[x]);
	}
	public static void union(int a,int b) {
		parent[a] = b;
	}
    public int solution(int[][] land, int height) {
        int answer = 0;
        int n = land[0].length;
        int mark =1;
        int visit[][] = new int[n][n];
        int dir[][] = {{1,0},{-1,0},{0,1},{0,-1}};
        ArrayDeque<int []> dq = new ArrayDeque<>();
        for(int i = 0 ; i < n ; i++) {
        	for(int j= 0 ; j < n ; j++) {
        		if(visit[i][j] ==0) {
        			visit[i][j] = mark;
        			dq.add(new int[] {i,j});
        			while(!dq.isEmpty()) {
        				int now[]  = dq.poll();
        				for(int k =0 ; k< 4; k++) {
        					int ny = dir[k][0] + now[0];
        					int nx = dir[k][1] + now[1];
        					if( ny >= 0 && nx >= 0 && ny < n && nx < n) {
        						if(visit[ny][nx]==0){
        							if(Math.abs(land[ny][nx] - land[now[0]][now[1]]) <= height) {
        								visit[ny][nx] = mark;
        								dq.add(new int[] {ny,nx});
        							}
        						}
        					}
        				}
        			}
        			mark++;
        		}
        	}
        }
        
        parent = new int[mark];
        for(int i = 0 ; i < mark; i++) {
        	parent[i] = i;
        }
        PriorityQueue<int []> pq = new PriorityQueue<>(new Comparator<int []>() {
        	@Override
        	public int compare(int[] o1, int[] o2) {
        		if(o1[2] > o2[2]) return 1;
        		else if( o1[2] < o2[2]) return -1;
        		else return 0;
        	}
		});
        for(int i = 0 ; i < n ; i++) {
        	for(int j= 0 ; j < n ; j++) {
        		for(int k = 0 ; k < 4 ; k ++) {
        			int ny = i + dir[k][0];
        			int nx = j + dir[k][1];
        			if(ny >= 0 && nx >= 0 && nx < n && ny < n) {
	        			if(visit[i][j] != visit[ny][nx]) {
	        				pq.add(new int[] {visit[i][j] ,visit[ny][nx] , Math.abs(land[ny][nx] - land[i][j])});
	        			}
        			}
        		}
        	}
        }
        
        int cnt = 1;
        while(cnt < mark-1) {
        	int now[] =pq.poll();
        	int pa = find(now[0]);
        	int pb = find(now[1]);
        	if(pa==pb) continue;
        	union(pa, pb);
        	cnt++;
        	answer += now[2];
        }
        return answer;
    }
}

---

 

---

문제를 풀고 생각났는데 간선을 우선순위 큐에 넣어줄때 현재 mark값보다 큰값만 넣어주면

간선의 중복을 해결할 수 있다. 나만몰랐넴..

for(int i = 0 ; i < n ; i++) {
        	for(int j= 0 ; j < n ; j++) {
        		for(int k = 0 ; k < 4 ; k ++) {
        			int ny = i + dir[k][0];
        			int nx = j + dir[k][1];
        			if(ny >= 0 && nx >= 0 && nx < n && ny < n) {
	        			if(visit[i][j] < visit[ny][nx]) {
	        				pq.add(new int[] {visit[i][j] ,visit[ny][nx] , Math.abs(land[ny][nx] - land[i][j])});
	        			}
        			}
        		}
        	}
        }