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

https://school.programmers.co.kr/learn/courses/30/lessons/62050?language=java#

프로그래머스

 

import java.util.*;
class Solution {
    public static int N, h, cnt = 0;
    public static int[] dr = {-1, 0, 1, 0};
    public static int[] dc = {0, 1, 0 ,-1};
    public static int[][] visited;
    public static PriorityQueue<int[]> pq = new PriorityQueue<>((o1, o2) -> Integer.compare(o1[2], o2[2]));
    
    public int solution(int[][] land, int height) {
        int answer = 0;
        N = land[0].length;
        h = height;
        visited = new int[N][N];
        
        pq.offer(new int[] {0, 0, 0});
        
        while(cnt < N * N){
            int[] cur = pq.poll();
            int cr = cur[0];
            int cc = cur[1];
            if(visited[cr][cc] == 1) continue;
            cnt += 1;
            answer += cur[2];
            dfs(land, cr, cc);
        }
        
        return answer;
    }
    
    public static void dfs(int[][] land, int sr, int sc){
        visited[sr][sc] = 1;
        for(int i = 0;i<4;i++){
            int nr = sr + dr[i];
            int nc = sc + dc[i];
            if(nr < 0 || nr >= N || nc < 0 || nc >= N) continue;
            if(visited[nr][nc] == 0){
                int cost = Math.abs(land[nr][nc] - land[sr][sc]);
                if(cost <= h){
                    cnt += 1;
                    dfs(land, nr, nc);
                } else{
                    pq.offer(new int[] {nr, nc, cost});
                }
            }
        }
    }
}

 

풀이 사항

풀이 일자: 2024.10.30
풀이 시간: 120분
채점 결과: 정답
예상 문제 유형: dfs, 우선순위큐
시간: 86.81ms(최악)
메모리: 93.4MB (최악)

풀이방법

1. 0, 0 부터 dfs탐색을 시작하는데 상하좌우로 접근하여 높이 차이가 h보다 작은값으로 재귀해주며 높이차이가 그보다 크면 해당 위치와 높이차이를 우선순위 큐에 저장해준다.
2. 모든 dfs 탐색이 끝났다면 우선순위 큐에서 높이차이가 가장 작은 값을 꺼내준다.
3. 방문하지 않은 위치라면 answer에 높이차이를 더해주고 dfs 탐색을 시작한다.