경주로 건설

문제 정보

• 프로그래머스 Lv.3
• DP
• 문제 링크

풀이

BFS + 방향 상태를 포함한 최단 비용 탐색 문제다.

단순 BFS로는 풀 수 없다. 같은 칸에 도달하더라도 어떤 방향으로 들어왔는지에 따라 이후 비용이 달라지기 때문이다.

따라서 상태를 (x, y, dir)로 정의하고, 각 상태에서의 최소 비용을 BFS로 탐색한다.

• DP 배열 = int[][][] cost = new int[n][n][4]: (x, y)에서 dir방향으로 갈 때의 최소 비용

코드

import java.util.*;
 
class Node {
    int x;
    int y;
    int dir;
    int cost;
    
    public Node (int x, int y, int dir, int cost) {
        this.x = x;
        this.y = y;
        this.dir = dir;
        this.cost = cost;
    }
}
 
class Solution {
    int[] dx = {-1, 0, 1, 0};
    int[] dy = {0, 1, 0, -1};
    
    public int solution(int[][] board) {
        int n = board.length;
        
        // 방향: 0 = 위, 1 = 오른쪽, 2 = 아래, 3 = 왼쪽
        int[][][] cost = new int[n][n][4];
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                Arrays.fill(cost[i][j], Integer.MAX_VALUE);
        
        Queue<Node> q = new LinkedList<>();
        
        // 출발점은 방향이 정해져 있지 않으므로 오른쪽, 아래 두 방향으로만 이동 가능
        cost[0][0][1] = 0;
        cost[0][0][2] = 0;
        q.add(new Node(0, 0, 1, 0));
        q.add(new Node(0, 0, 2, 0));
        
        while (!q.isEmpty()) {
            Node cur = q.poll();
            
            if (cur.cost > cost[cur.x][cur.y][cur.dir])
                continue;
            
            for (int i = 0; i < 4; i++) {
                int nx = cur.x + dx[i];
                int ny = cur.y + dy[i];
                
                if (nx < 0 || ny < 0 || nx >= n || ny >= n)
                    continue;
                if (board[nx][ny] == 1)
                    continue;
                
                int nextCost = cur.cost + (cur.dir == i ? 100 : 600);
                
                if (cost[nx][ny][i] > nextCost) {
                    cost[nx][ny][i] = nextCost;
                    q.add(new Node(nx, ny, i, nextCost));
                }
            }
        }
        
        int answer = Integer.MAX_VALUE;
        for (int i = 0; i < 4; i++)
            answer = Math.min(answer, cost[n - 1][n - 1][i]);
        
        return answer;
    }
}