백준 2206번 : 벽 부수고 이동하기 풀이(Java)

www.acmicpc.net/problem/2206

2206번: 벽 부수고 이동하기

모든 틀림을 다 겪었다

Key Point

1. 나는 처음 접근할 때 1000*1000 인줄 모르고 벽을 부술 때 마다 BFS를 다시 돌리는 것으로 생각했다. 당연히 시간초과로 털렸다.

2. 이 문제에서 가장 중요한 것은 무조건 한번의 BFS 내에서 해결해야 한다는 것이다. 위와 동일한 얘기지만, 이 점이 굉장히 어려웠다.

3. 질문 검색을 조금 보고나서 기존의 visited 배열을 2차원에서 3차원으로 확장해야 한다는 것을 알았다.

이 문제는 벽을 단 한번 부술 수 있으므로,

visited[x][y][0](벽을 아직 안 부순 경우) 과 visited[x][y][1] ( 벽을 부수고 온 경우 ) 로 나뉘어 생각해야 한다.

벽을 여러 번 부술 수 있다면 3차원 을 그 횟수에 맞춰 확장해야 하지 않을까 싶은데, 나중에 풀어봐야 겠다.

4. 또한, 큐를 돌면서 도착 지점에 도착했다고 바로 리턴해서 끝내 버리면 안 된다. 반드시 큐가 완전히 빌 때까지 다 돌면서 "최단" 거리를 찾아야 한다.

 

Solution

1. (0,0) 에서 시작하고, (0,0) 은 무조건 벽이 없으므로 visitied[0][0][0] = true; 로 방문 체크를 해준다.

2. 큐에 (0,0) 노드를 담아준다. 이 때 거리를 나타내는 depth 는 1부터 시작임을 잊지 말자.

3. 이 후 늘 하던 BFS 처럼 상하좌우를 순회한다.

4. 

if(sx == N-1 && sy == M-1) {
  ans = Math.min(ans, sd);
  continue;
}

Key Point 에서 언급한 4번을 담당하는 코드이다. 도착 했다고 바로 끝내면 안 된다!!

5. 배열의 범위를 벗어나는 다음 지점들은 continue로 넘겨준다.

6. 

if(visited[sx][sy][0]) {
    if(visited[nx][ny][0]) continue;
    if(map[nx][ny] == 1) {
      visited[nx][ny][1] = true;
    } else {
      visited[nx][ny][0] = true;
  }
} else if(visited[sx][sy][1]) {
    if(visited[nx][ny][1]) continue;
    if(map[nx][ny] == 1) {
      continue;
    } else {
      visited[nx][ny][1] = true;
    }
}

여기서 분기가 갈린다. 시작 지점인 sx, sy 에서 만약에 0번, 즉 벽을 안 부수고 지나온 경우가 true 일 경우에,

벽을 부수지 않은 채로 다음 지점에 가는 경우가 이미 방문한 경우라면 넘겨준다. 안 해주면 당연히 무한 루프가 돌 것이다.

만약 다음 지점에 벽이 있다면,

다음 지점의 1번을 true로 , 즉 다음 지점 부터는 벽을 부순 경우로 생각하라고 남겨주는 것이다.

벽이 없다면, 다음 지점의 0번을 true로 해서 다음 지점에서도 벽을 부수지 않은 경우로 생각하라고 남겨준다.

 

반대로, 시작 지점에서 벽을 부수고 지나온 경우가 true일 경우,

벽을 부순 채로 다음 지점에 가는 경우가 이미 방문한 경우라면 넘겨준다. 마찬가지로 무한 루프 방지.

만약 다음 지점에 벽이 있다면, 이미 한 번 부쉈으므로 그 지점에 갈 수 없다. 넘겨준다.

벽이 없다면, 벽을 부쉈다는 것을 기록하기 위해 visited[nx][ny][1] = true 로 기록을 남겨준다.

이후 하던 것 처럼 기존 거리 + 1 을 큐에 기록해준다.

 

전체 코드

package boj.BFS_DFS;
import java.io.*;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main_벽부수고이동하기_2206 {
    static BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
    static int N,M, ans = Integer.MAX_VALUE;
    static int[][] map;
    static int[] dx = {-1,1,0,0};
    static int[] dy = {0,0,-1,1};

    static class Node {
        int x;
        int y;
        int depth;

        public Node(int x, int y, int depth) {
            this.x = x;
            this.y = y;
            this.depth = depth;
        }
    }

    static void input() throws IOException {
        StringTokenizer nm = new StringTokenizer(bufferedReader.readLine());
        N = Integer.parseInt(nm.nextToken());
        M = Integer.parseInt(nm.nextToken());
        map = new int[N][M];
        for(int i = 0 ; i < N; i++) {
            char[] line = bufferedReader.readLine().toCharArray();
            for(int j = 0; j < M; j++) {
                map[i][j] = Integer.parseInt(Character.toString(line[j]));
            }
        }
    }

    static void bfs(boolean[][][] visited) {
        Queue<Node> queue = new LinkedList<>();
        visited[0][0][0] = true; 
        queue.add(new Node(0,0,1));
        while (!queue.isEmpty()) {
            Node start = queue.poll();
            int sx = start.x;
            int sy = start.y;
            int sd = start.depth;
            if(sx == N-1 && sy == M-1) {
                ans = Math.min(ans, sd);
                continue;
            }
            for(int i = 0 ; i < 4; i++) {
                int nx = sx + dx[i];
                int ny = sy + dy[i];
                if(nx < 0 || ny < 0 || nx >= N || ny >= M) continue;
                if(visited[sx][sy][0]) {
                    if(visited[nx][ny][0]) continue;
                    if(map[nx][ny] == 1) {
                        visited[nx][ny][1] = true;
                    } else {
                        visited[nx][ny][0] = true;
                    }
                } else if(visited[sx][sy][1]) {
                    if(visited[nx][ny][1]) continue;
                    if(map[nx][ny] == 1) {
                        continue;
                    } else {
                        visited[nx][ny][1] = true;
                    }
                }
                queue.add(new Node(nx, ny, sd+1));
            }
        }
    }

    static void solve() {
        bfs(new boolean[N][M][2]);
        if(ans == Integer.MAX_VALUE) {
            System.out.println(-1);
        } else {
            System.out.println(ans);
        }
    }

    public static void main(String[] args) throws IOException {
        input();
        solve();
        bufferedReader.close();
    }
}