https://www.acmicpc.net/problem/2206
기본 bfs에서 벽을 부수고 이동할 수 있다는 조건이 추가된 문제이다. 벽을 부순 적이 있는지 없는지 구분하는 것이 포인트인데 이 부분을 생각하지 못했다. 고민하다가 3차원 배열로 해결할 수 있다는 힌트를 얻고 문제를 해결하였다.
크게 두 가지 경우의 수로 나눌 수 있는데 이전에 벽을 부수지 않은 경우와 벽을 부순 경우이다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
/**
* (1,1) -> (N,M) 최단 경로 구하기
* 만약, 이동이 불가능할 경우 -1 출력
* 조건) 벽을 부수고 이동할 경우 거리가 짧아진다면 1개의 벽을 부술 수 있음
* 한 번도 벽을 부순 적이 없다면, 벽 부수고 이동 가능
* 한 번이라도 벽을 부순 적이 있다면, 벽 부수고 이동 불가능
*/
public class b2206 {
static int n; // 행
static int m; // 열
static int[][] map;
static boolean[][][] check;
static int[] dx = {1, 0, -1, 0}, dy = {0, 1, 0, -1};
static Queue<Point> queue;
public static void main(String[] args) throws IOException {
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][m];
// 방문 여부와 벽 부순 여부를 구분하기 위해 3차원 배열로 선언
// 0이면 벽을 부순 적이 없음
// 1이면 벽을 부순 적이 있음
check = new boolean[n][m][2];
for (int i = 0; i < n; i++) {
String input = br.readLine();
for (int j = 0; j < m; j++) {
map[i][j] = input.charAt(j) - '0';
}
}
bfs(0, 0);
}
public static void bfs(int x, int y) {
queue = new LinkedList<>();
// 시작점도 포함
queue.add(new Point(x, y, 1, 0));
while (!queue.isEmpty()) {
Point point = queue.poll();
// 도착지점을 만나면 종료
if (point.x == n - 1 && point.y == m - 1) {
System.out.println(point.cnt);
return;
}
for (int i = 0; i < 4; i++) {
int nx = point.x + dx[i];
int ny = point.y + dy[i];
/**
* 1. 벽을 부순 적이 없는 경우
* - 벽인 경우
* => 벽을 부수고 거리 +1, 방문처리
* - 벽이 아닌 경우
* => 거리 +1, 방문처리
* 2. 벽을 부순 적이 있는 경우
* - 벽이 아닌 경우만 체크
* - 거리 +1, 방문처리
*/
if (nx >= 0 && ny >= 0 && nx < n && ny < m) {
// 이전에 벽을 부순 적이 없고 방문하지 않았다면
if (point.destroyed == 0 && !check[nx][ny][0]) {
// 벽인 경우
if (map[nx][ny] == 1) {
// 벽을 부수고 거리 +1, 방문처리
queue.add(new Point(nx, ny, point.cnt + 1, point.destroyed + 1));
check[nx][ny][1] = true;
} else { // 벽이 아닌 경우
queue.add(new Point(nx, ny, point.cnt + 1, point.destroyed));
check[nx][ny][0] = true;
}
// 이전에 벽을 부순 적이 있고 방문하지 않았다면
} else if (point.destroyed == 1 && !check[nx][ny][1]) {
if (map[nx][ny] == 0) { // 벽이 아닌 경우만 체크
queue.add(new Point(nx, ny, point.cnt + 1, point.destroyed));
check[nx][ny][1] = true;
}
}
}
}
}
System.out.println(-1);
}
}
class Point {
int x;
int y;
int cnt;
int destroyed;
public Point(int x, int y, int cnt, int destroyed) {
this.x = x;
this.y = y;
this.cnt = cnt;
this.destroyed = destroyed;
}
}