[프로그래머스] 경주로 건설 - BFS

풀이

한지점 -> 특정 지점 까지의 최단거리이므로 BFS로 풀면 될거라 생각했다.
기본적인 BFS라 생각했으나 테스트케이스에서 계속 틀려서 고민을 많이 했다.

놓친점 1

평소 백준문제를 풀때는 board가 input으로 주어져서 x와 y를 board[x][y]로 편하게 지정할 수 있었지만, 여기서는 x가 가로축으로 설정하려면 board[y][x]여야 했다. 그래서 계속 값이 이상하게 나왔었다.

놓친점 2

이렇게 풀었는데 24번 테스트 케이스가 계속 틀렸었다. 그 이유는 특정 지점에서 고유값은 단순히 Cost 가 아니라 방향도 포함된다.

즉, 동쪽으로 이동하면서 Cost가 800인것과 남쪽으로 이동하면서 Cost가 900 인것 중 어떤것 을 선택해야 할까?

여기선 판단할 수 없으므로 두 가지 모두 값을 저장하고 루프를 지속해야 한다.

int[][][] value = new int[4][n][n]; 여기서 이런식으로 4가지 방향을 선언해주었고 이후 마지막에 4가지 값중 가장 작은 값을 채택했다.

이후 BFS 중 문제가 생기면 value값이 문제조건에 대해 유일할 수 있는지 확인보자.

최종 코드

class Solution {
    public int solution(int[][] board) {
        
        int n =board.length;
        
        
        board[0][0]=1;
        int[][][] value = new int[4][n][n];

        bfs(0,0,0,0,board, value, n);
        bfs(0,0,2,0,board, value, n);

        int ans = Integer.MAX_VALUE;
        
        for (int i = 0; i < 4; i++) {
            if (value[i][n-1][n-1]==0){
                continue;
            }
            ans = Math.min(ans,value[i][n-1][n-1]);
        }
        return ans;
    }
    
    public static void bfs(int y,int x, int type,int cost, int[][] board, int[][][] value,int n){
        value[type][y][x]=cost;

        // 동서남북
        int[] dx = {1,-1,0,0};
        int[] dy = {0,0,1,-1};

        for (int i = 0; i < 4; i++) {
            int ny = dy[i] + y;
            int nx = dx[i] + x;

            // 속해있지 않으면 continue
            if (!(nx >= 0 && nx < n && ny >= 0 && ny < n)){
                continue;
            }

            if (board[ny][nx] == 1){
                continue;
            }

            int nextCost =0;
            if (type==i){
                // 방향이 같거나 시작점인 경우
                nextCost = cost+100;
            }
            else{
                nextCost = cost+600;
            }

            if (value[i][ny][nx]==0 || nextCost <= value[i][ny][nx] ) {
                bfs(ny, nx, i, nextCost,board,value,n);
            }
        }
    }
}