[BOJ] 14442. 벽 부수고 이동하기2

이 문제는 BFS를 활용한 문제였다.

문제를 맨처음 접했을 때 당연하게 2차원 visit배열을 이용하여 벽을 만났을 때 현재 위치에서 남은 벽 부수는 횟수를 이용하여 단순하게 벽을 부수는 방법으로 접근을 하였다. 이러한 경우 다음과 같은 문제점이 발생하게 된다.

0 1 1 1
0 0 1 0
이러한 맵이 부술수 있는 벽이 1개 존재한다고 가정하자. 이 상황에서 최단 거리는 당연히 직관적으로 (1,1) -> (2,1) -> (2,2) -> (2,3 부수기) -> (2,4)를 확인 할 수가 있다. 다만 맨처음에 접근했던 방법을 이용하여 BFS를 돌았을 때 단지 벽부는 횟수만 체크하게 된다면 (1,1) -> (1,2 부수기) -> (2,2) 에서 끝나는 상황을 충분히 마주치게 된다. 그러므로 벽 부수는 것에 대해서 따로 구별을 해줘야한다.

따라서 벽 부수는 횟수가 첨부된 3차원 visit 배열(visti[가로][세로][벽부순횟수])을 사용해보았다. 이게 이문제에서 가장 큰 포인트였다. 

package algosutdy1;
 
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class Main_bj_14442_벽부수고이동하기2 {
    static class Pos {
        int i, j, breakCount;
 
        public Pos(int i, int j, int breakCount) {
            this.i = i;
            this.j = j;
            this.breakCount = breakCount;
        }
    }
 
    static int N, M, K;
    static int[][] map;
    static int[][][] visit;
 
    static Queue<Pos> queue;
    static int[] di = {-1, 0, 1, 0};
    static int[] dj = {0, 1, 0, -1};
 
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
 
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());
 
        map = new int[N][M];
        visit = new int[N][M][K + 1];        //[가로][세로][벽을뚫은횟수]
 
        for (int i = 0; i < N; i++) {
            String input = br.readLine();
            for (int j = 0; j < M; j++) {
                map[i][j] = input.charAt(j) - '0';
                for (int k = 0; k <= K; k++) {
                    visit[i][j][k] = -1;
                }
            }
        }
 
        queue = new LinkedList<>();
 
        bfs();
 
        int result = Integer.MAX_VALUE;
        for (int i = 0; i <= K; i++) {
            if (visit[N - 1][M - 1][i] != -1) {
                result = Math.min(result, visit[N - 1][M - 1][i]);
            }
        }
 
        if (result == Integer.MAX_VALUE) {
            System.out.println(-1);
        } else {
            System.out.println(result);
        }
    }
 
    static void bfs() {
        queue.offer(new Pos(0, 0, 0));
        visit[0][0][0] = 1;
 
        while (!queue.isEmpty()) {
            Pos cur = queue.poll();
 
            if (cur.i == N - 1 && cur.j == M - 1) {
                continue;
            }
 
            for (int dir = 0; dir < 4; dir++) {
                int nextI = cur.i + di[dir];
                int nextJ = cur.j + dj[dir];
 
                if (nextI < 0 || nextI >= N || nextJ < 0 || nextJ >= M) {
                    continue;
                }
 
                if (cur.breakCount == K) {        //벽뚫기 횟수를 모두 사용한 경우
                    if (map[nextI][nextJ] == 0 && visit[nextI][nextJ][cur.breakCount] == -1) {
                        queue.offer(new Pos(nextI, nextJ, cur.breakCount));
                        visit[nextI][nextJ][cur.breakCount] = visit[cur.i][cur.j][cur.breakCount] + 1;
                    }
                } else {                        //벽을 뚫을 수 있는 경우
                    if (map[nextI][nextJ] == 0 && visit[nextI][nextJ][cur.breakCount] == -1) {        //벽이 아닌 경우
                        queue.offer(new Pos(nextI, nextJ, cur.breakCount));
                        visit[nextI][nextJ][cur.breakCount] = visit[cur.i][cur.j][cur.breakCount] + 1;
                    } else if (map[nextI][nextJ] == 1 && visit[nextI][nextJ][cur.breakCount + 1] == -1) {        //벽인 경우
                        queue.offer(new Pos(nextI, nextJ, cur.breakCount + 1));
                        visit[nextI][nextJ][cur.breakCount + 1] = visit[cur.i][cur.j][cur.breakCount] + 1;
                    }
                }
            }
        }
 
    }
 
}