백준 2206: 벽을 부순 상태까지 나누어 BFS하기
백준 2206번 ‘벽 부수고 이동하기’는 0으로 표시된 길을 따라 시작점에서 도착점까지 이동하는 문제입니다. 1은 벽이지만 이동 중 한 번은 벽을 부술 수 있습니다.
기존 BFS에 벽을 한 번 부술 수 있다는 조건을 어떻게 넣으면 될까요? 좌표만으로 방문을 구분하면 벽을 부술 기회가 남아 있는지 알 수 없습니다.
좌표만 방문 처리했을 때 놓친 것
처음에는 BFS를 재귀적으로 다시 호출하는 방식을 생각했습니다. 벽을 부수지 않았을 때는 false, 한 번 부순 뒤에는 true를 넘겨 탐색하는 방식이었습니다.
같은 칸에 같은 거리로 도착하더라도 이후에 할 수 있는 일이 달라서 문제가 됐습니다. 벽을 이미 부순 경로가 먼저 방문 표시를 하면 벽을 부수지 않고 도착하는 경로가 막혔습니다. 아직 남아 있던 기회를 잃는 셈이었습니다.
당시에는 앞선 시도에서도 방문 배열을 3차원으로 만들면 해결할 수 있겠다고 생각했습니다. 하지만 그 방식을 계속 고치는 대신 큐에 상태를 함께 넣는 풀이로 다시 진행했습니다. 앞선 재귀 방식에서 방문 배열만 나누면 최단 거리 탐색까지 보장되는지는 따로 봐야 합니다.
같은 좌표라도 두 상태로 구분합니다
visited[x][y][0]은 벽을 부수지 않은 상태, visited[x][y][1]은 이미 한 번 부순 상태를 뜻하도록 했습니다. Pos에는 좌표 외에도 이동 거리 cnt와 벽을 부순 여부 hit를 저장했습니다. 지도 자체에는 거리를 덮어쓰지 않습니다.
다음 칸이 길이면 현재 상태를 유지해 이동합니다. 다음 칸이 벽이면 아직 벽을 부수지 않은 경우에만 이동하며 벽을 부순 상태로 바뀝니다.
시작 칸과 도착 칸을 모두 세므로 cnt는 1부터 시작합니다. 큐에서 꺼낸 좌표가 도착점이면 그 거리를 반환합니다. 끝까지 도착하지 못하면 -1을 반환합니다.
문자 입력을 정수로 바꿉니다
지도 입력은 다음과 같이 처리했습니다.
String line = br.readLine();charAt()으로 얻은 '0', '1'은 정수 0, 1과 다릅니다. 당시 코드에서는 문자 '0'의 값인 48을 빼서 정수로 바꿨습니다.
방문 인덱스에 문제가 남은 코드
아래 코드에서 벽으로 이동하는 분기를 보면 큐에는 hit = 1인 상태를 넣습니다. 그런데 방문 확인과 표시는 visited[newX][newY][now.hit], 즉 인덱스 0에 하고 있습니다. 앞서 설명한 상태의 의미와 맞추려면 도착 상태인 1을 확인하고 표시해야 합니다. 이 오류가 남아 있으므로 그대로 정답 코드로 사용하면 안 됩니다. 인덱스를 수정한 뒤의 동작과 채점 결과도 별도로 확인해야 합니다.
import java.io.*;
import java.util.*;
class Main {
static int N, M;
static Queue<Pos> q = new LinkedList<>();
static boolean[][][] visited;
static int[][] map;
static int[] opsX = {1, -1, 0 ,0};
static int[] opsY = {0, 0, 1, -1};
static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
static StringTokenizer st;
static class Pos {
int x;
int y;
int cnt;
int hit;
public Pos(int x, int y, int cnt, int hit) {
this.x = x;
this.y = y;
this.cnt = cnt;
this.hit = hit;
}
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
st = new StringTokenizer(br.readLine(), " ");
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
map = new int[N][M];
visited = new boolean[N][M][2];
for (int i = 0; i < N; i++) {
String line = br.readLine();
for (int j = 0; j < line.length(); j++) {
map[i][j] = line.charAt(j) - 48;
}
}
bw.write(String.valueOf(bfs(new Pos(0,0,1,0))));
bw.flush();
}
public static int bfs(Pos node) {
q.offer(new Pos(node.x, node.y, node.cnt, node.hit));
visited[node.x][node.y][node.hit] = true;
while (!q.isEmpty()) {
Pos now = q.poll();
if (now.x == N-1 && now.y == M-1) {
return now.cnt;
}
for (int i = 0; i < 4; i++) {
int newX = now.x + opsX[i];
int newY = now.y + opsY[i];
if (checkRange(newX, newY)) {
// 다음 이동할 곳이 그냥 길인 경우
if (map[newX][newY] == 0 && !visited[newX][newY][now.hit]) {
q.offer(new Pos(newX, newY, now.cnt+1, now.hit));
visited[newX][newY][now.hit] = true;
}
// 다음 이동할 곳이 벽인데 벽을 부지 않은 경우
if (now.hit == 0 && map[newX][newY] == 1 && !visited[newX][newY][now.hit]) {
q.offer(new Pos(newX, newY, now.cnt+1, now.hit+1));
visited[newX][newY][now.hit] = true;
}
}
}
}
return -1;
}
public static boolean checkRange(int x, int y) {
return -1 < x && x < N && -1 < y && y < M;
}
}