[프로그래머스/LV3] 경주로 건설 - 다익스트라 (Java)

[프로그래머스/LV3] 경주로 건설

🙋‍♂️ 들어가며

이번 문제는 다익스트라를 활용하여 비용을 pq로 오름차순하여 맨 마지막 도착지에서 4방향을 탐색하고 제일 싼 비용을 구한다.

첫 시작점은 우측, 아래 총 2개를 pq에 넣고 시작한다.

✅ 정답 코드

// 다익스트라
import java.util.PriorityQueue;
import java.util.Arrays;



class Solution {
    static int[] dr = {-1,1,0,0};
    static int[] dc = {0,0,-1,1};
    static int N;
    static int min_cost = Integer.MAX_VALUE;
    
    
    
    public int solution(int[][] board) {
        N = board.length;
        
        // 1. 다익스트라를 위한 비용배열 INF로 채우기
        int[][][] cost_arr = new int[N][N][4];
        for (int r = 0; r < N; r++) {
            for (int c = 0; c < N; c++) {
                Arrays.fill(cost_arr[r][c], Integer.MAX_VALUE);
            }
        }
        
        // 2. 시작점 초기화
        int sr = 0;
        int sc = 0;
        int er = N-1;
        int ec = N-1;
        for (int d = 0; d < 4; d++) {
            cost_arr[sr][sc][d] = 0;
        }
        
        // 3-1. pq 생성 (비용 오름차순)
        PriorityQueue<int[]> pq = new PriorityQueue<>( (a,b) -> a[3] - b[3] );
        int cost_sum = 0;
        
        // 3-2. 첫위치 삽입 (오른쪽으로, 아래로)
        pq.offer(new int[] {sr, sc, 1, cost_sum});
        pq.offer(new int[] {sr, sc, 3, cost_sum});
        
        // 4. 탐색
        while (!pq.isEmpty()) {
            int[] cur_pos = pq.poll();
            int cr = cur_pos[0];
            int cc = cur_pos[1];
            int prev_d = cur_pos[2];
            int cur_cost = cur_pos[3];
            
            // 4-1. 만약 끝점 도달시 return
            if (cr == er && cc == ec) {
                return cur_cost;
            }
            
            // 4-2. 다 도달 못했으면
            for (int d = 0; d < 4; d++) {
                int nr = cr + dr[d];
                int nc = cc + dc[d];
                
                // 4-3. 범위 벗어나면 skip
                if (nr < 0 || nr >= N || nc < 0 || nc >= N) continue;
                
                // 4-4. 벽이면 skip
                if (board[nr][nc] == 1) continue;
                
                // 4-5. 범위 안이고, 빈칸이라면
                // 비용 계산
                int next_cost = cur_cost + 100;
                if (prev_d != d) {
                    next_cost += 500;
                }
                
                // 4-6. 새 비용이 작거나 같으면 갱신
                if (next_cost <= cost_arr[nr][nc][d]) {
                    cost_arr[nr][nc][d] = next_cost;
                    pq.offer(new int[] {nr, nc, d, next_cost});
                }
                
            } 
            
            
        }
        
        // 5. 목적지에서 4방향 중 최소비용 찾기
        int min_cost = Integer.MAX_VALUE;
        for (int d = 0; d < 4; d++) {
            min_cost = Math.min(min_cost, cost_arr[N-1][N-1][d]);
        }
        return min_cost;
    }
}