출처: https://www.acmicpc.net/problem/2206
N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로로 이동하려 한다. 최단경로는 맵에서 가장 적은 개수의 칸을 지나는 경로를 말하는데, 이때 시작하는 칸과 끝나는 칸도 포함해서 센다.
만약에 이동하는 도중에 한 개의 벽을 부수고 이동하는 것이 좀 더 경로가 짧아진다면, 벽을 한 개 까지 부수고 이동하여도 된다.
한 칸에서 이동할 수 있는 칸은 상하좌우로 인접한 칸이다.
맵이 주어졌을 때, 최단 경로를 구해 내는 프로그램을 작성하시오.
입력 형식
첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 1,000)이 주어진다. 다음 N개의 줄에 M개의 숫자로 맵이 주어진다. (1, 1)과 (N, M)은 항상 0이라고 가정하자.
출력 형식
첫째 줄에 최단 거리를 출력한다. 불가능할 때는 -1을 출력한다.
예제 입력 1
6 4 0100 1110 1000 0000 0111 0000
예제 출력 1
15
예제 입력 2
4 4 0111 1111 1111 1110
예제 출력 2
-1
import java.util.*;
public class Main {
static class Node {
int x, y, wallBroken, dist;
Node(int x, int y, int wallBroken, int dist) {
this.x = x;
this.y = y;
this.wallBroken = wallBroken;
this.dist = dist;
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int m = sc.nextInt();
sc.nextLine();
int[][] grid = new int[n][m];
for (int i = 0; i < n; i++) {
String line = sc.nextLine();
for (int j = 0; j < m; j++) {
grid[i][j] = line.charAt(j) - '0';
}
}
System.out.println(bfs(n, m, grid));
}
public static int bfs(int n, int m, int[][] grid) {
int[][][] visited = new int[n][m][2]; // 3차원 방문 배열
Queue queue = new LinkedList<>();
queue.add(new Node(0, 0, 0, 1));
visited[0][0][0] = 1;
int[][] directions = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
while (!queue.isEmpty()) {
Node current = queue.poll();
int x = current.x;
int y = current.y;
int wallBroken = current.wallBroken;
int dist = current.dist;
// (N, M)에 도달한 경우
if (____) {
return dist;
}
for (int[] direction : directions) {
int nx = x + direction[0];
int ny = y + direction[1];
if (nx >= 0 && nx < n && ny >= 0 && ny < m) { // 유효한 범위인지 확인
// 벽을 만나지 않은 경우
if (__) {
visited[nx][ny][wallBroken] = 1;
queue.add(new Node(nx, ny, wallBroken, dist + 1));
}
// 벽을 만났지만 아직 부술 수 있는 경우
else if (__) {
visited[nx][ny][1] = 1;
queue.add(new Node(nx, ny, 1, dist + 1));
}
}
}
}
return -1; // 목표 지점에 도달할 수 없는 경우
}
}
빈칸1 : X
정답: x == n - 1 && y == m - 1
해설: 문제의 목표는 시작점 (0, 0)에서 끝점 (N-1, M-1)로 이동하는 것입니다. (0,0)부터 BFS를 사용해 탐색하며, 도달 조건은 끝점 좌표 (N-1, M-1)을 기준으로 확인해야 합니다.
-> 나는 x == n && y == m 을 선택했다. 끝점 (N-1, M-1)라는 생각을 못했기 때문이었다.
빈칸2 : O
정답: grid[nx][ny] == 0 && visited[nx][ny][wallBroken] == 0
해설: 벽을 만나지 않고 이동하기 위해서는 다음 조건을 만족해야 합니다. 이동하려는 칸이 벽이 아니어야(grid[nx][ny] == 0) 하며 현재 상태에서 방문한 적이 없어야(visited[nx][ny][wallBroken] == 0) 합니다.
빈칸3 : O
정답: grid[nx][ny] == 1 && wallBroken == 0 && visited[nx][ny][1] == 0
해설: 벽을 만났지만 부술 수 있는 경우에는 다음 조건을 만족해야 합니다. 이동하려는 칸이 벽이어야 합니다(grid[nx][ny] == 1). 아직 벽을 부술 기회가 남아 있어야 합니다(wallBroken == 0). 벽을 부순 상태에서 해당 칸을 방문한 적이 없어야 합니다(visited[nx][ny][1] == 0).
