N * M의 행렬에서 0은 이동 가능한 곳, 1은 벽을 나타낸다. 이때 (1, 1)에서 (N, M)까지 최단 거리로 이동하려고 한다. 이동하면서 딱 한 번의 벽을 부수고 이동할 수 있고, 안 부시고 이동해도 된다. 이때 최단 경로를 구해내는 프로그램을 작성해라.
최단 거리를 구해야하기 때문에 BFS로 풀이했다. 이 문제에서 중요했던 건, 딱 한 번만 벽을 부술 수 있다는 점이었다.
그래서 원래는 boolean 변수로 벽을 부쉈는지를 체크했었는데 실핻 도중에 진짜 딱 한번만 부숴짐ㅜㅜ..
그래서 3차원 boolean 배열로 부쉈을 때와 안부쉈을 때의 방문 체크를 분리했다.
또 객체에 벽을 부순 적 있는지와 이동 거리를 함께 저장하며 기록했다.
다음에 가야하는 위치가
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
public class BOJ_2206 {
static int N;
static int M;
static int[][] map;
static int[] dx = {0, 0, -1, 1};
static int[] dy = {-1, 1, 0, 0};
static boolean[][][] visited;
public static void main(String[] args) throws Exception{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] input = br.readLine().split(" ");
N = Integer.parseInt(input[0]);
M = Integer.parseInt(input[1]);
map = new int[N+1][M+1];
visited = new boolean[N+1][M+1][2];
for (int i = 1; i <= N; i++) {
input = br.readLine().split("");
for (int j = 1; j <= M; j++) {
map[i][j] = Integer.parseInt(input[j-1]);
}
}
bfs(1, 1);
}
static void bfs(int x, int y) {
Queue<Point> q = new LinkedList<>();
q.add(new Point(x, y, 0, 1));
visited[x][y][0] = true;
visited[x][y][1] = true;
while (!q.isEmpty()) {
Point p = q.poll();
if (p.x == N && p.y == M) {
System.out.println(p.count);
return;
}
for (int i = 0; i < 4; i++) {
int nx = p.x + dx[i];
int ny = p.y + dy[i];
int breakWall = p.breakWall;
int count = p.count;
if (nx <= 0 || ny <= 0 || nx > N || ny > M) continue;
if(map[nx][ny] == 1) { //벽
if (breakWall == 0 && !visited[nx][ny][1]) { //벽을 부신 적 없음
visited[nx][ny][1] = true;
q.add(new Point(nx, ny, 1, count + 1));
}
} else { //빈 칸
if(!visited[nx][ny][breakWall]) {
q.add(new Point(nx, ny, breakWall, count + 1));
visited[nx][ny][breakWall] = true;
}
}
}
}
System.out.println(-1);
}
static class Point {
int x; int y;
int breakWall;
int count;
public Point(int x, int y, int breakWall, int count) {
this.x = x;
this.y = y;
this.breakWall = breakWall;
this.count = count;
}
}
}