백준 2206(JAVA)

문제

N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로로 이동하려 한다. 최단경로는 맵에서 가장 적은 개수의 칸을 지나는 경로를 말하는데, 이때 시작하는 칸과 끝나는 칸도 포함해서 센다.

만약에 이동하는 도중에 한 개의 벽을 부수고 이동하는 것이 좀 더 경로가 짧아진다면, 벽을 한 개 까지 부수고 이동하여도 된다.

한 칸에서 이동할 수 있는 칸은 상하좌우로 인접한 칸이다.

맵이 주어졌을 때, 최단 경로를 구해 내는 프로그램을 작성하시오.

풀이

일단 가중치없는 그래프에서 최단 경로이므로 BFS로 풀어야하는 것은 눈치를 챘다.
그런데,,, 쉽게 풀줄 알았던 문제가 발목을 잡았다.(이틀정도 고민함)
벽을 한개만 부술수 있으므로 큐에 넣는 상태는 벽을 부순 적이 있냐, 벽을 부순 적이 없냐의 상태도 저장해야한다.
여기까진 생각할수 있다.

그런데 자꾸 틀리는 것이다..
왜그럴까 생각을 했는데 벽을 부순상태에서 온 거리와 벽을 부수지 않은 상태에서 온 거리중 뭐가 짧은지 알수가 없기 때문이다.

좋은 반례가 아래에 있다.

5 4
0001
1101
0001
0111
0010

그래서 방문처리를 할 visited 2차원 배열을 3차원 배열로 바꾸어서, 벽을 부수지 않은 상태에서의 방문처리, 벽을 부순 상태에서의 방문처리를 따로해야한다.
결국 (N, M)에 도달할 것은 BFS이므로 가장 빨리온녀석이 도달할 것이다.

이 부분만 잘 해결하면 쉽게 풀수 있다.. (그러나 방문처리할 배열을 3차원으로 생각하는 부분이 힘들었다. 따지고놓고보면 힘들지만 힘들지않다(?). 벽을 부순상태에서의 거리와 벽을 부수지 않은 상태에서의 거리중 뭐가 짧은지 알수가 없기 때문에..)

코드

package baekjoon.그래프탐색;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main2206 {
    static int N, M;
    static int[][] board;
    static boolean[][][] visited;
    static int[] dx = {-1, 0, 1, 0};
    static int[] dy = {0, -1, 0, 1};
    static int result = -1;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        visited = new boolean[N][M][2];
        board = new int[N][M];
        for(int i = 0; i < N; i++){
            String str = br.readLine();
            for(int j = 0; j < M; j++){
                if(str.charAt(j) == '0'){
                    board[i][j] = 0;
                }else{
                    board[i][j] = -1;
                }
            }
        }

        bfs();

        System.out.println(result);
    }
    static void bfs(){
        Queue<Person> q = new LinkedList<>();
        q.offer(new Person(0, 0, 0, false));
        visited[0][0][0] = true;

        while(!q.isEmpty()){
            Person current = q.poll();
            if(current.x == N - 1 && current.y == M - 1) {
                result = current.count + 1;
                return;
            }
            for(int i = 0; i < 4; i++){
                int nextX = current.x + dx[i];
                int nextY = current.y + dy[i];

                if(nextX < 0 || nextX >= N || nextY < 0 || nextY >= M) continue;
                if(board[nextX][nextY] == -1){
                    //가려는 곳이 벽이면
                    if(visited[nextX][nextY][1]) continue; //방문했다면
                    if(current.isBroke)continue;
                    //가려는 곳이 벽인데 부순적이 있다면
                    else{
                        //가려는 곳이 벽인데 부순적이 없다면
                        visited[nextX][nextY][1] = true;
                        q.offer(new Person(nextX, nextY, current.count + 1, true));
                    }
                }else{
                    //가려는 곳이 벽이아니면
                    if(current.isBroke){
                        //벽을 부순적이있으면
                        if(visited[nextX][nextY][1]) continue;
                        else{
                            visited[nextX][nextY][1] = true;
                            q.offer(new Person(nextX, nextY, current.count + 1, current.isBroke));
                        }
                    }else{
                        //벽을 부순적이 없으면
                        if(visited[nextX][nextY][0]) continue;
                        else{
                            visited[nextX][nextY][0] = true;
                            q.offer(new Person(nextX, nextY, current.count + 1, current.isBroke));
                        }
                    }
                }
            }
        }

    }
}
class Person{
    int x;
    int y;
    int count;
    boolean isBroke;

    public Person(int x, int y, int count, boolean isBroke) {
        this.x = x;
        this.y = y;
        this.count = count;
        this.isBroke = isBroke;
    }

    @Override
    public String toString() {
        return "Person{" +
                "x=" + x +
                ", y=" + y +
                ", count=" + count +
                ", isBroke=" + isBroke +
                '}';
    }
}