문제

BOJ 2206: 벽 부수고 이동하기 https://www.acmicpc.net/problem/2206

풀이

우선 최단 경로를 묻는 문제기 때문에 BFS를 사용하여 해결한다. 하지만 벽을 한 개 까지는 부수고 이동할 수 있다.

• 부순 벽의 수가 0개 이다 -> 1. 벽을 부수고 이동한다. 2. 벽을 하나도 부수지 않고 이동한다.
• 부순 벽의 수가 1개 이상이다 -> 벽을 부수지 못한다.

벽을 하나도 부수지 않고 최단거리로 도착하는 경우와 벽을 하나 부수고 최단거리로 도착하는 경우를 구분하여
visited[N][M][2] 의 3차원 배열으로 처리하였다.
visited[N][M][0]은 벽을 부수지 않고 탐색한 경우, visited[N][M][1]은 벽을 하나 부수고 탐색한 경우이다.

BFS 함수 안 쪽에

• 길인가?
  • 아직 벽을 하나도 부수지 않았다. -> visited[N][M][0]에 true를 통해 방문 처리 + Queue에 넣음
  • 벽을 이미 하나 부쉈다. -> visited[N][M][1]에 true를 통해 방문 처리 + Queue에 넣음
• 벽인가?
  • 벽을 아직 하나도 부수지 않았다.
  • 벽을 부순다. -> visited[N][M][1]에 true를 통해 방문 처리 + Queue에 넣음
  • 이미 벽을 하나 부순 상태이다. -> 아무것도 할 수 없으므로 통과

코드

import java.util.*;
import java.io.*;

public class Main {

    static int N, M;
    static int[][] map;
    static boolean[][][] visited;
    static int[] dx = {0, 0, 1, -1};
    static int[] dy = {1, -1, 0, 0};

    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        String[] inputs = br.readLine().split(" ");
        N = Integer.parseInt(inputs[0]);
        M = Integer.parseInt(inputs[1]);

        map = new int[N][M];
        visited = new boolean[N][M][2];

        for(int i=0; i<N; i++) {
            String str = br.readLine();
            for(int j=0; j<M; j++) {
                map[i][j] = str.charAt(j) - '0';
            }
        }

        int answer = bfs(0, 0);

        if(answer == -1) {
            System.out.println(-1);
        } else {
            System.out.println(answer);
        }

    }

    static int bfs(int x, int y) {
        Queue<Pos> que = new LinkedList<>();

        que.add(new Pos(x, y, 1, false));
        visited[x][y][0] = true;

        while(!que.isEmpty()) {
            Pos p = que.poll();

            int curX = p.x;
            int curY = p.y;

            if(curX == N-1 && curY == M-1) { // 도착함
                return p.cnt;
            }

            for(int t=0; t<4; t++) {
                int nx = curX + dx[t];
                int ny = curY + dy[t];

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

                if(map[nx][ny] == 0) { // 지나갈 수 있는 길 이면?
                    if(!visited[nx][ny][0] && !p.isDestroyed) { // 벽을 하나도 안 부쉈다면
                        que.add(new Pos(nx, ny, p.cnt + 1, false)); //벽 안 부수고 거리 추가
                        visited[nx][ny][0] = true; 
                    } else if(!visited[nx][ny][1] && p.isDestroyed) { // 벽을 한 번 부수 적이 있으면
                        que.add(new Pos(nx, ny, p.cnt + 1, true));
                        visited[nx][ny][1] = true;
                    }
                } else if(map[nx][ny] == 1) { // 벽이면?
                    if(!p.isDestroyed) {//벽을 하나도 안 부쉇으면 -> 하나 부수고 통과함
                        que.add(new Pos(nx, ny, p.cnt + 1, true));
                        visited[nx][ny][1] = true; // 하나 부쉇으니깐 [1]로 감
                    } else { // 벽을 한 번 부순 적 잇으면?
                        //아무것도 안함
                    }
                }
            }

        }
        return -1;
    }

    static class Pos{
        int x;
        int y;
        int cnt;
        boolean isDestroyed;

        Pos(int x, int y, int cnt, boolean isDestroyed){
            this.x = x;
            this.y = y;
            this.cnt = cnt;
            this.isDestroyed = isDestroyed;
        }
    }
}

정리

• 예외적인 경우(벽을 부순다거나 벽이 이동한다거나)가 있을 때 방문 처리와 탐색 방법을 어떻게 해야 할 지 고민할 수 있는 문제였다.
• 3차원 배열을 통해 각각 처리하는 방법이 신선했다.