SWEA 1249. [S/W 문제해결 응용] 4일차 - 보급로

class SupplyRoute
{
    static int N;
    static int[][] map;
    static int[][] cost;
    static int[] dr = {1,0,-1,0};
    static int[] dc = {0,1,0,-1};
    static int min;
    public static void main(String args[]) throws Exception
    {
        Scanner sc = new Scanner(System.in);
        int T;
        T=sc.nextInt();
        for(int test_case = 1; test_case <= T; test_case++)
        {
            N = sc.nextInt();
            min =Integer.MAX_VALUE;
            map = new int[N][N];
            cost = new int[N][N];
            for(int i  =0; i<N; i++){
                String str = sc.next();
                for(int j = 0; j<N; j++){
                    map[i][j] = str.charAt(j)-'0';
                    cost[i][j] = Integer.MAX_VALUE;
                }
            }
            cost[0][0] = 0;
            bfs(0,0);
            System.out.println("#"+test_case+" "+cost[N-1][N-1]);
        }
    }
    public static void bfs(int row, int col){
        Queue<int[]> que = new LinkedList<>();
        que.add(new int[]{row,col});
        while(!que.isEmpty()){
            int[] current = que.poll();
            int crow = current[0];
            int ccol = current[1];
            for(int i = 0; i<4; i++){
                int nrow = crow + dr[i];
                int ncol = ccol + dc[i];
                if(nrow<0||ncol<0||nrow>=N||ncol>=N)
                    continue;
                if(cost[nrow][ncol]>cost[crow][ccol]+map[nrow][ncol]){
                    cost[nrow][ncol]=cost[crow][ccol]+map[nrow][ncol];
                    que.add(new int[]{nrow,ncol});
                }
            }
        }
    }

}

풀이방법

맵을 bfs로 탐색하며, 누적합을 따로 저장, 비교하는 방식으로 설계한다.

1. 초기에 cost를 전부 MAX_VALUE로 초기화시킨다.
2. cost[0][0] = 0으로 하고, bfs탐색을 시작한다.
   
3. 누적합을 저장하며 탐색하고, 중복탐색이 허용되야 한다.
   📢단, 현재 탐색 방법이 기존에 저장되어 있던 누적합보다 작다면, 현재 탐색 방법으로 누적합을 대체한다.
4. 마지막 칸의 누적합을 출력해주면, 최소루트가 된다.

후기

처음보는 유형의 bfs 탐색이었다. 처음에는 dfs + 완탐으로 최소루트를 찾아야하나부터, 백트래킹, DP 방식을 써야하나 했는데,
이런 방법이 있었다.
방법만 안다면 구현은 어렵지 않았는데, 신기한 유형이었다.