[백준 2206번] 벽 부수고 이동하기 (java)

문제

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

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

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

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

입력

첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 1,000)이 주어진다. 다음 N개의 줄에 M개의 숫자로 맵이 주어진다. (1, 1)과 (N, M)은 항상 0이라고 가정하자.

출력

첫째 줄에 최단 거리를 출력한다. 불가능할 때는 -1을 출력한다.

---

정답

처음에는 1번 부술수 있는 벽들을 탐색해서 리스트에 담고 리스트에 있는 벽을 하나씩 지워서 탐색한것중에 가장 짧은 거리를 구해냈다.(리스트의 길이만큼 너비탐색을 반복했다.) 근데 이런식으로 풀게 되니 계속해서 시간초과가 떴다. 이 문제는 이런식으로는 절대로 풀지 못한다.
이 문제에서는 벽을 한번도 안부순 경우와 벽을 한번 부수고 이동하는 경우로 나눠서 생각해야 한다. 그러므로 visited배열은 2차원이 아닌 3차원 배열이 되어야한다.
visited[n][m][0]은 벽을 한번도 안부순 애들이 탐색한 경우, visited[n][m][1]은 벽을 한번 부수고 탐색한 경우이다.
원래 최단경로 문제는 미로에 경로의 길이를 입력하면서 가야하지만 이 문제는 큐에 넣는 노드 값이 경로 길이를 포함시켜서 탐색해야 한다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.Queue;

public class Main {
    static int n,m;
    static int[][] maze;
    static int [] dx = {0,0,1,-1};
    static int [] dy = {1,-1,0,0};
    static Queue<Pair> que = new LinkedList<Pair>();
    static boolean[][][] visited;


    public static void BFS() {
        visited = new boolean[n][m][2];    //[][][0]은 벽은 안 부신 경우, [][][1]은 벽은 부신경우
        visited[0][0][0] = true;
        visited[0][0][1] = true;
        que.add(new Pair(0,0,1,0));

        int ans=Integer.MAX_VALUE;
        while(!que.isEmpty()) {
            Pair node = que.poll();
            int nodex = node.x;
            int nodey = node.y;
            int nodelength = node.length;
            int nodewall = node.wall;

            if(nodex == n-1 && nodey == m-1) {
                ans = Math.min(ans,  nodelength);
                continue;
            }
            //주변 칸을 탐색
            /**
             * 이전에 벽은 부수지 않은경우(wall==0) 2가지
             * 0-1 벽을 만났을때는 벽을 안 부쉈으므로 벽 부수고 이동 wall을 1로 바꿈
             * 0-2 벽을 만나지 않았을때, 그대로 방문처리해주고 탐색을 계속
             * 이전에 벽을 부순경우(wall==1) 2가지
             * 1-1 벽을 만났을 경우, 이미 벽을 부쉈으므로 탐색을 해당지점에서 종료 -> 큐에 값을 넣지 않는다는 뜻
             * 1-2 벽을 만나지 않은 경우, 그대로 방문처리를 하고탐색을 계속
             * **/ 
            for(int i=0;i<4;i++) {
                int nx = node.x + dx[i];
                int ny = node.y + dy[i];

                //범위 안일때
                if(nx>=0 && ny>=0 && nx<n && ny<m) {
                    //이전에 벽을 부수지 않은 경우이면서 방문하지 않는 곳이면
                    if(nodewall == 0 && !visited[nx][ny][0]) {
                        if(maze[nx][ny] == 1) {//벽일때
                            que.add(new Pair(nx,ny,nodelength+1,nodewall+1));
                            visited[nx][ny][1] = true;
                        }else {
                            que.add(new Pair(nx,ny,nodelength+1,nodewall));
                            visited[nx][ny][0] = true;
                        }
                    }else if(nodewall == 1 && !visited[nx][ny][1]) {//이전에 벽을 부순경우
                        if(maze[nx][ny]==0) {//벽이 아닐대만 체크
                            que.add(new Pair(nx,ny,nodelength+1,nodewall));
                            visited[nx][ny][1] = true;
                        }
                    }

                }
            }
        }
        if(ans == Integer.MAX_VALUE) {
            System.out.println("-1");
        }else {
            System.out.println(ans);
        }
    }
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));    

        String [] NM = br.readLine().split(" ");
        n = Integer.parseInt(NM[0]);
        m = Integer.parseInt(NM[1]);
        maze = new int[n][m];

        for(int i=0;i<n;i++) {
            String mazeinfo = br.readLine();
            for(int j=0;j<mazeinfo.length();j++) {
                maze[i][j] = Integer.parseInt(mazeinfo.substring(j, j+1));
            }
        }
        //너비탐색으로 부실수 있는 벽 체크
        BFS();

    }
    public static class Pair{
        int x,y;
        int length;
        int wall;
        public Pair(int x, int y, int length, int wall) {
            this.x = x;
            this.y = y;
            this.length = length;
            this.wall = wall;
        }
    }
}