프로그래머스 - 지형 이동

해당 알고리즘 자료는 제가 직접 푼 것도 있지만 다른 분들의 풀이과의 비교를 통해 더 나은 알고리즘을 공부하기 위해 정리한 것들입니다.

프로그래머스 - 지형 이동

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

풀이 : 최저값의 x,y를 찾아 Dfs 알고리즘을 통해 층 높이가 h 이하인 곳을 전부 방문한다. h 이상인 곳은 PriorityQueue에 집어넣어 Dfs 알고리즘 방식으로 cost를 추가하고 다시 Dfs 알고리즘을 통해 방문여부를 확인한다.

import java.util.*;
class Solution {
    static int [][] arr;
    static boolean [][] chk;
    static int cost = 0, cnt = 0;
    static PriorityQueue <int []> pq = new PriorityQueue<int []>((a,b) -> Math.abs(a[2]-a[3])-Math.abs(b[2]-b[3]));
    public int solution(int[][] land, int height) {
        int n = land.length,  x = 0, y = 0, min = Integer.MAX_VALUE;;
	arr = new int [n+2][n+2];
	chk = new boolean [n+2][n+2]; 
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if(land[i][j] < min) {
				min = land[i][j];
				y = i+1;
				x = j+1;
			}
			arr[1+i][1+j] = land[i][j];
		}
	}
	while(cnt < n*n) {
		visit(x,y, height);
		while(!pq.isEmpty()) {
			int [] data = pq.poll();
			if(!chk[data[1]][data[0]]) {
				x = data[0];
				y = data[1];
				cost += Math.abs(data[2] - data[3]);
				break;
			}
		}
	}
       return cost;
    }
    private static void visit(int a, int b, int h) {
	while(!pq.isEmpty()) {
		if(chk[pq.peek()[1]][pq.peek()[0]]) pq.poll();
		else break;
	}
	cnt++;
	chk[b][a] = true;
	int [] dx = {0, 0, 1, -1};
	int [] dy = {1, -1, 0, 0};
	for (int i = 0; i < 4; i++) {
		int nx = a + dx[i];
		int ny = b + dy[i];
		if(arr[ny][nx] != 0 && !chk[ny][nx]) {
			if(Math.abs(arr[ny][nx] - arr[b][a]) <= h) {
				visit(nx, ny, h);
			}
			else {
				pq.add(new int [] {nx, ny, arr[ny][nx], arr[b][a] });
			}
		}
	}
}
}