[BOJ 2206] 벽 부수고 가기 (Java)

문제

https://www.acmicpc.net/problem/2206

2206번: 벽 부수고 이동하기

 

풀이

이런 문제 유형은 처음이라, 쉽사리 해결 방법이 생각나지 않았다.

질문 게시판 힌트를 보고 풀었다. 

 

일단 기본 뼈대는 BFS로 구현한다. 

이후 벽 한개를 어떻게 파괴할 것인가? 이 문제에 맞닥뜨린다.

벽을 최대 한 개 파괴할 수 있지만 반드시 파괴해야 하는 것은 아니다. 

 

이 문제의 핵심은 방문 체크에 있다.

보통 좌표의 방문체크를 2차배열로 구현하지만,

해당 문제의 경우 벽 파괴 여부에 따라 방문체크를 별도로 하기 위해 아래와 같이 3차 배열로 구현한다.

visited[x][y][0] : 벽을 부수지 않고 해당 좌표 방문 여부

visited[x][y][1] : 벽을 부수고 해당 좌표 방문 여부

 

별도로 방문 체크해야 하는 이유는, 벽을 부수고 왔을 때랑 부수지 않고 왔을때의 최단 경로가 다를 수 있기 때문이다. 

 

Example)

5 5
00000
11110
10000
10111
10000

0	0	0	0	0
1	1	1	1	0
1	0	0	0	0
1	0	1	1	1
1	0	0	0	0

 

x: 1, y: 1, cnt : 1, destroyed : 0
x: 2, y: 1, cnt : 2, destroyed : 1
x: 1, y: 2, cnt : 2, destroyed : 0
x: 1, y: 1, cnt : 3, destroyed : 1
x: 2, y: 2, cnt : 3, destroyed : 1
x: 1, y: 3, cnt : 3, destroyed : 0
x: 1, y: 2, cnt : 4, destroyed : 1
x: 3, y: 2, cnt : 4, destroyed : 1
x: 2, y: 3, cnt : 4, destroyed : 1
x: 1, y: 4, cnt : 4, destroyed : 0
x: 1, y: 3, cnt : 5, destroyed : 1
x: 4, y: 2, cnt : 5, destroyed : 1
x: 3, y: 3, cnt : 5, destroyed : 1
x: 2, y: 4, cnt : 5, destroyed : 1
x: 1, y: 5, cnt : 5, destroyed : 0
x: 1, y: 4, cnt : 6, destroyed : 1
x: 5, y: 2, cnt : 6, destroyed : 1
x: 3, y: 4, cnt : 6, destroyed : 1
x: 2, y: 5, cnt : 6, destroyed : 1
x: 2, y: 5, cnt : 6, destroyed : 0
x: 1, y: 5, cnt : 7, destroyed : 1
x: 5, y: 3, cnt : 7, destroyed : 1
x: 3, y: 5, cnt : 7, destroyed : 1
x: 3, y: 5, cnt : 7, destroyed : 0
x: 5, y: 4, cnt : 8, destroyed : 1
x: 4, y: 5, cnt : 8, destroyed : 1
x: 3, y: 4, cnt : 8, destroyed : 0
x: 5, y: 5, cnt : 9, destroyed : 1
9

자세한 설명은 소스코드에 작성하였다.

소스코드

package bfs;

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

public class BOJ2206 {

    public static int N, M;
    public static int[][] map;
    public static boolean[][][] visited;
    public static int[][] dir = new int[][]{{1, 0}, {-1, 0}, {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());
        map = new int[N+1][M+1];
        visited = new boolean[N+1][M+1][2]; // 0 벽을 안부시고 온 경우, 1 벽을 부수고 온 경우

        for(int i = 1; i <= N; i++){
            char[] arr = br.readLine().toCharArray();
            for(int j = 1; j <=M ; j++){
                map[i][j] = Integer.parseInt(String.valueOf(arr[j-1]));
            }
        }
        System.out.println(bfs());
    }


    public static int bfs(){
        // none 0, destroyed 1
        int answer = -1;
        Queue<Integer> que = new LinkedList<Integer>();
        que.add(1); // x
        que.add(1); // y
        que.add(1); // cnt
        que.add(0); // destroyed
        visited[1][1][0] = true; // visited[x][y][0] -> 벽 안부수고 온 경우의 방문체크 / visited[x][y][1] 벽 부수고 온 경우 방문체크

        while(!que.isEmpty()){
            int x = que.poll();
            int y = que.poll();
            int cnt = que.poll();
            int destroyed = que.poll();

//            System.out.println("x: "+x + ", y: "+ y + ", cnt : " + cnt + ", destroyed : "+destroyed);

            if(x == N && y == M){
                answer = cnt;
                break;
            }

            for(int[] d : dir){
                int nx = x + d[0];
                int ny = y + d[1];
                int nCnt = cnt + 1;

                if(nx < 1 || ny < 1 || nx > N || ny > M) continue;

                // 경로를 지나오면서 아직 벽이 부숴지지 않은 경우
                if(map[nx][ny] == 1){
                    // 벽이다!
                    // 경로를 지나오면서 이미 벽을 한 번 부수고 온 경우, 이 좌표를 갈 수 없음.
                    if(destroyed == 1) continue;

                    // 벽 안부수고 왔어? 그러면 벽 부수자.
                    // 근데 이 경로 지난적 있나?
                    if(visited[nx][ny][1]) continue;
                    visited[nx][ny][1] = true;

                    que.offer(nx);
                    que.offer(ny);
                    que.offer(nCnt);
                    // 다음 좌표부터는 벽이 이미 부숴졌으니, 벽을 부술 수 없는 것을 알려줘야 함.
                    que.offer(1);
                } else {
                    // 벽이 아니다!
                    if(visited[nx][ny][destroyed]) continue;
                    visited[nx][ny][destroyed] = true;
                    que.offer(nx);
                    que.offer(ny);
                    que.offer(nCnt);
                    que.offer(destroyed);

                }
            }
        }

        return answer;
    }

}