BFS

프로그래머스 2020 카카오 인턴십 Level 3 경주로 건설 문제를 Java로 풀어보았다.
처음에는 별 생각 없이 BFS로 풀었다가 테스트 케이스 중 일부가 돌아가지 않는 걸 보고 어떤 오류가 있는지 고민해보았다.

먼저 처음 틀렸던 코드다.

import java.util.Queue;
import java.util.LinkedList;

class Solution {
    static int[][] price;
    static int N;
    static int[][] move = { {-1,0}, {1,0}, {0,-1}, {0,1} }; // 상하좌우
    
    public int solution(int[][] board) {
        N = board.length;
        price = new int[N][N];
        for(int i=0; i<N; i++){
            for(int j=0; j<N; j++)
                price[i][j] = Integer.MAX_VALUE;
        }
        Queue<int[]> q = new LinkedList<>();
        q.add(new int[]{0,0,-1});  price[0][0] = 0;

        while(!q.isEmpty()){
            int[] cur = q.poll();

            for(int i=0; i<4; i++){
                int nRow = cur[0] + move[i][0]; int nCol = cur[1] + move[i][1];
                if(!isInRange(nRow, nCol) || board[nRow][nCol]==1)   continue;
                if(cur[2]==-1){ // 출발 지점에서는 그냥 100만 추가하고 지나감
                    q.add(new int[]{nRow,nCol,i});
                    price[nRow][nCol] = 100;
                    continue;
                }
                if(cur[2]!=i) { // 방향이 달라질 경우
                    if(cur[2]+i==1 || cur[2]+i==5)  continue; // 역방향으로 돌아가면 넘겨
                    if(price[nRow][nCol]<price[cur[0]][cur[1]]+600) continue;
                    q.add(new int[]{nRow,nCol,i});
                    price[nRow][nCol] = price[cur[0]][cur[1]] + 600;
                }
                else{ // 직선으로 갈 경우
                    if(price[nRow][nCol]<price[cur[0]][cur[1]]+100) continue;
                    q.add(new int[]{nRow, nCol, i});
                    price[nRow][nCol] = price[cur[0]][cur[1]] + 100;
                }
            }
        }

        return price[N-1][N-1];
    }
    
    static Boolean isInRange(int row, int col){
        if(row<0 || row>=N || col<0 || col>=N)  return false;
        return true;
    }
}

int[][] price를 보면 2차원 배열로 선언한 것을 볼 수 있다.
어떤 문제가 발생할 수 있는지 살펴보자. 여러 경로로부터 동일한 칸에 도착했을 때 더 작은 값으로 해당 칸의 값을 갱신하게 되면, 그 다음 움직임이 코너 움직임인지 직선 움직임인지에 따라서 다음 값이 역전될 수 있다.
위 그림을 살펴보면 1번 움직임과 2번 움직임이 각각 2600원과 2700원이라고 가정해보자. 그렇다면 그 다음 움직임은 동일하게 우측으로 이동하는 움직임일 때, 더 작았던 1번 움직임의 2600원은 2600+600=3200원이 되지만 2번 움직임은 2700+100=2800원이 된다.

이런 경우를 방지해주기 위해서는 어떤 작업을 해줄 수 있을까?

---

방향별로 따로 처리하기

위에서 발생한 오류를 보자마자 떠오른 것은 방향별로 따로 계산한다면 어떤 경로에서 왔든지간에 겹칠 일이 발생하지 않는다. 그러면 저렇게 두 개 이상의 경로 간의 역전 현상도 걱정할 필요가 없게된다.

각 방향별로 가장 작은 건설 비용들로 갱신되는 것이다.

3차원 배열을 보통 잘 쓰지 않지만 3차원 배열로 해결하면 복잡하게 생각할 필요없이 직관적으로 해결이 가능하다.

나는 이 경로별로 각 칸마다 얼마의 건설 비용이 드는지 흔적을 남기며 이 문제를 풀었다. 이를 위해서 int[][][] price라는 배열을 선언했다.

price = new int[4][N][N]; // 방향, 행, 열

---

결국 다음 방향값까지 고려한 3차원 배열을 이용해 도착점까지 간 후에, 도착점의 서로 다른 네 방향 중 가장 작은 값을 반환해주면 된다.

전체 코드는 아래와 같다.

import java.util.Queue;
import java.util.LinkedList;
import java.io.*;

public class RaceTrack {
    static int[][][] price;
    static int N;
    static int[][] move = { {-1,0}, {1,0}, {0,-1}, {0,1} }; // 상하좌우

    static int solution(int[][] board) {
        N = board.length;
        price = new int[4][N][N]; // 방향, 행, 열
        for(int i=0; i<N; i++){
            for(int j=0; j<N; j++) {
                price[0][i][j] = Integer.MAX_VALUE; price[1][i][j] = Integer.MAX_VALUE;
                price[2][i][j] = Integer.MAX_VALUE; price[3][i][j] = Integer.MAX_VALUE;
            }
        }
        Queue<int[]> q = new LinkedList<>();
        if(board[1][0]==0){
            price[1][1][0] = 100;
            q.add(new int[]{1,0,1});
        }
        if(board[0][1]==0){
            price[3][0][1] = 100;
            q.add(new int[]{0,1,3});
        }

        while(!q.isEmpty()){
            int[] cur = q.poll();
            int cRow = cur[0];  int cCol = cur[1];  int cDir = cur[2];

            for(int nDir=0; nDir<4; nDir++){
                int nRow = cRow + move[nDir][0]; int nCol = cCol + move[nDir][1];
                if(!isInRange(nRow, nCol) || board[nRow][nCol]==1)   continue;
                if(cDir!=nDir) { // 방향이 달라질 경우
                    if(cDir+nDir==1 || cDir+nDir==5)  continue; // 역방향으로 돌아가면 넘겨
                    if(price[nDir][nRow][nCol]<price[cDir][cRow][cCol]+600) continue;
                    q.add(new int[]{nRow,nCol,nDir});
                    price[nDir][nRow][nCol] = price[cDir][cRow][cCol] + 600;
                }
                else{ // 직선으로 갈 경우
                    if(price[nDir][nRow][nCol]<price[cDir][cRow][cCol]+100) continue;
                    q.add(new int[]{nRow, nCol, nDir});
                    price[nDir][nRow][nCol] = price[cDir][cRow][cCol] + 100;
                }
            }
        }
        int result = Integer.MAX_VALUE;
        for(int i=0; i<4; i++)
            result = (result>price[i][N-1][N-1] ? price[i][N-1][N-1]:result);
        return result;
    }

    static Boolean isInRange(int row, int col){
        if(row<0 || row>=N || col<0 || col>=N)  return false;
        return true;
    }
}

문제에서 주어진 Test Case 만으로는 어떤 부분이 틀렸는지 확인하기 어렵다. 나도 결국 내가 틀린 Test Case 를 검색해보며 어떤 부분이 틀렸는지 알아냈는데... 실제 시험 상황을 고려했을 때는 반례를 빠르게 찾아내 코드를 수정하는 능력도 필요하겠단 생각이 든다...어렵다..ㅠ..

---

2022.03.01 재시도 ( 실패 )

이번에는 PriorityQueue를 이용해서 다시 풀어봤는데 방향을 가로 세로 두 개만으로 잡고 풀었더니 틀렸다. 네 방향을 모두 다 적용해줘야 하는 것...

큐가 빌 때까지 while문을 돌 것이 아니라, 현재 경로의 가격을 기준으로 오름차순 정렬을 시키는 우선 순위 큐를 이용하면 도착점을 만나자마자 바로 while문을 종료할 수 있기 때문에 우선 순위 큐를 이용하는 것을 생각해봤다.

아이디어 자체는 좋았으나 네 방향을 모두 고려하지 않았더니 틀렸다. 솔직히 가로 세로 두 방향만 이용한 것이 왜 틀렸는지 엄밀한 논리적 이유는 못 찾았다. 그냥.. 4방향 처리해서 다시 풀었더니 통과됐다... 하...

방문 처리 ( 4방향 )

이미 다른 경로를 통해서 방문된 적이 있는 위치의 가격이 새롭게 가고 있는 경로의 가격보다 이미 작으면 패스해주는 처리를 생각하지 못했는데 이게 주요했던 것 같다.

아래는 내가 제출한 코드다.

import java.util.PriorityQueue;
import java.io.*;

public class RaceTrack {
    static int[][][] visited; // 4 방향별 방문 정보
    static int[][] dir = { {-1,0}, {1,0}, {0,-1}, {0,1} }; // 상하좌우

    static int solution(int[][] board) {
        int n = board.length;
        int answer = 0;
        visited = new int[n][n][4];
        PriorityQueue<Info> q = new PriorityQueue<>();

        visited[0][0][0] = visited[0][0][1] = visited[0][0][2] = visited[0][0][3] = -1;
        if(board[0][1]==0) {
            q.add(new Info(0, 1, 3,1));
            visited[0][1][0] = 1;
        }
        if(board[1][0]==0) {
            q.add(new Info(1, 0, 1,1));
            visited[1][0][1] = 1;
        }

        while(!q.isEmpty()){
            Info cur = q.poll();
            if(cur.row==n-1 && cur.col==n-1){
                answer = cur.price;
                break;
            }

            for(int n_dir=0; n_dir<4; n_dir++){
                int n_row = cur.row + dir[n_dir][0];
                int n_col = cur.col + dir[n_dir][1];
                int n_price = cur.price + ((cur.dir == n_dir) ? 1 : 6);

                if(n_row<0 || n_row>=n || n_col<0 || n_col>=n || board[n_row][n_col]==1)  continue; // 범위 밖 OR 벽이면 패스
                if(visited[n_row][n_col][n_dir]!=0 && visited[n_row][n_col][n_dir] < n_price)    continue; // 이미 방문했으면 패스

                visited[n_row][n_col][n_dir] = n_price;
                q.add(new Info(n_row,n_col,n_dir,n_price));
            }
        }

        return answer*100;
    }

    static class Info implements Comparable<Info> { // 위치, 방향, 가격 정보 담은 클래스
        int row;
        int col;
        int dir;
        int price;

        Info(int row, int col, int dir, int price){
            this.row = row;
            this.col = col;
            this.dir = dir;
            this.price = price;
        }

        @Override
        public int compareTo(Info cmp){ // 가격 기준으로 정렬
            return this.price - cmp.price;
        }
    }

    public static void main(String args[]) throws IOException {
        BufferedWriter bfw = new BufferedWriter(new OutputStreamWriter(System.out));
        int[][] board = {{0,0,0,0,0,0,0,1},{0,0,0,0,0,0,0,0},{0,0,0,0,0,1,0,0},{0,0,0,0,1,0,0,0},{0,0,0,1,0,0,0,1},{0,0,1,0,0,0,1,0},{0,1,0,0,0,1,0,0},{1,0,0,0,0,0,0,0}};
        bfw.write(String.valueOf(solution(board)));
        bfw.close();
    }
}

몇 번을 풀어도 제자리 ㅎ...썅