Today I Learned

오늘은 꽤 어려운 문제를 풀었다. bfs에서 확장된 문제인데 dp를 3차원 배열까지 확장시켜 풀었다.

경주로 건설

문제

N x N 경주로 부지에 1 x 1 크기의 도로 격자를 설치하려 한다. 직선 구간은 100원, 코너 구간은 500원의 비용이 발생한다. 이차원 배열로 주어지는 설계도면에서 0은 도로를 설치할 수 있고, 1은 벽이 있어 도로가 지나갈 수 없다. (0,0)에서 (N-1,N-1)까지 가는 최소 비용을 구하라.

풀이과정

1. 우선 그래프상에서 최단 구간을 탐색하는 구조라 바로 bfs를 활용했다.
   단, bfs는 최소 경로가 나오면 바로 종료되지만, 이 문제는 도로에 비용 조건이 따로 있고 타일을 더 설치하더라도 비용이 적게 나올 수 있는 경우가 있기 때문에 이점을 유의해야 한다.

2. 우선 Road 클래스를 만들어 도로에 필요한 정보를 저장한다. x,y좌표와 방향, 누적 비용이 필요하다.

3. 방문 여부를 저장할 visited 배열을 만든다.

4. bfs이므로 큐를 만들어 첫 도로인 0,0 좌표의 Road 클래스를 넣는다.

5. while문으로 큐가 빌때 까지 4방향으로 bfs 탐색을 진행한다. 단, 문제에서는 코너에서 500원이 필요하다고 되어있지만 그림을 자세히 보면 코너 + 직선이기 때문에 결국 600원이 필요하다. 이래서 문제를 잘 읽어봐야 한다.

6. 이렇게 해서 나온 최소비용을 dp로 활용하기 위해 2차원 배열에 저장한다. 기존 방식보다 비용이 저렴할때만 저장하도록 해서 경로마다 비용을 기록한다.

7. 최종적으로 n-1,n-1 좌표에서 가장 적은 비용이 return된다.

Trouble : 3차원 DP 기록 배열

• 마지막 25번째 케이스만 통과되지 않아 애를 먹었다. 어떤 방법을 써도 안돼서 다른 사람의 풀이를 참고했다.

• 결론은 방문을 처리하는 visited 배열을 2차원이 아니라 3차원으로 만들어야 한다는 것이다. 이미 한 번 방문했더라도 어떤 방향으로 오냐에 따라 경우 자체가 달라지기때문에 방향별로 다르게 봐야한다는 것이다.

• 그래서 visited 배열은 int[n][n][4]로 만들고 첫 값만 4군데를 true로 만들고 다음번 방문처리때는 해당 방향에만 true로 방문처리를 해 체크하면 마지막 케이스도 제대로 풀린다.

Java 코드

import java.util.*;
public class Road {
    int x;
    int y;
    int direction;
    int cost;
    
    Road(int x, int y, int direction, int cost) {
        this.x = x;
        this.y = y;
        this.direction = direction;
        this.cost = cost;
    }
}

class Solution {
    boolean[][][] visited;
    int[] xMove = {1,0,-1,0};
    int[] yMove = {0,1,0,-1};
    final int st = 100;
    final int cn = 500;
    
    public int bfs(int[][] board){
        int n = board.length;
        int[][] map = board;
        int min = Integer.MAX_VALUE;
        
        Queue<Road> q = new ArrayDeque<>();
        
        q.offer(new Road(0,0,-1,0));
        for(int i=0; i<4; i++){
            visited[0][0][i] = true;
        }
        while(!q.isEmpty()){
            Road road = q.poll();
            int tmpX = road.x;
            int tmpY = road.y;
            int tmpD = road.direction;
            int tmpC = road.cost;
            
            if(tmpX==n-1 && tmpY==n-1){
                min = Math.min(min,tmpC);
            }
            
            for(int i=0; i<4; i++){
                int newX = tmpX + xMove[i];
                int newY = tmpY + yMove[i];
                if(newX<0 || newY<0 || newX>=n || newY>=n || board[newX][newY]==1) continue;
                
                int newC = tmpC;
                if(tmpD==-1 || tmpD == i){
                    newC += st;
                } else {
                    newC += cn + st;
                }
                
                if(!visited[newX][newY][i] || map[newX][newY] >= newC){
                    visited[newX][newY][i] = true;
                    map[newX][newY] = newC;
                    q.offer(new Road(newX, newY, i, newC));
                }
                
                
            }
            
        }
        return min;
    }
    
    public int solution(int[][] board) {
        visited = new boolean[board.length][board.length][4];
        return bfs(board);
    }
}