목차
문제파악
n*m으로 이루어진 맵에서 (0, 0) 지점에서 (n-1, m-1)까지 가는 최단 거리를 구하는 문제입니다.
따라서 bfs 알고리즘을 활용하면 되겠죠?!
하지만! 여기서 주의할 점은.. 벽을 한 번 부수고 이동할 수 있다는 것입니다.
이 점을 유의해서 문제를 해결해야 합니다.
해결 방법
일반적인 bfs문제 해결과 같이 큐를 활용하고, 방문한 지점을 큐에 넣고 상하좌우로 이동하면서 판단합니다.
이 문제에서 핵심은 벽을 한 번 부수고 이동할 수 있다는 것인데, 그로 인해 최단 거리를 두 가지 경우로 나누어보아야합니다.
- 벽을 한 번 부수고 이동한 것
- 벽을 부수지 않고 이동한 것
벽을 부수고 이동한 경로인지 부수지 않고 이동한 경로인지 알기 위해서 visited 배열을 3중배열로 선언해줍니다.
그래야 위와 같은 두 가지 경우를 다 고려해볼 수 있습니다.
핵심 코드
static void bfs(int[][] maze, int n, int m) {
int[] dx = { -1, 1, 0, 0 };
int[] dy = { 0, 0, -1, 1 };
int answer = -1;
int distance = 0;
boolean[][][] visited = new boolean[n][m][2]; // 맨 마지막 0이면, 벽 안뚫고 간거!
Queue<Point> queue = new LinkedList<>();
queue.offer(new Point(0, 0, 1, false));
visited[0][0][0] = true;
while (!queue.isEmpty()) {
Point tmp = queue.poll();
int x = tmp.x;
int y = tmp.y;
boolean b = tmp.isCracked;
distance = tmp.distance;
if (x == n - 1 && y == m - 1) {
answer = distance;
break;
}
for (int i = 0; i < 4; i++) {
int nx = x + dx[i];
int ny = y + dy[i];
if (nx < 0 || nx >= n || ny < 0 || ny >= m) {
continue;
}
if (maze[nx][ny] == 1) {
if (!b && !visited[nx][ny][1]) { // 벽을 부숨
queue.offer(new Point(nx, ny, distance + 1, true));
visited[nx][ny][1] = true;
}
} else {
if (!b && !visited[nx][ny][0]) { // 벽을 안부수고 가는 경우
queue.offer(new Point(nx, ny, distance + 1, b));
visited[nx][ny][0] = true;
}
if (b && !visited[nx][ny][1]) { // 벽을 부수고 가는 경우
queue.offer(new Point(nx, ny, distance + 1, b));
visited[nx][ny][1] = true;
}
}
}
}
System.out.println(answer);
}전체 소스 코드는 여기서 확인하실 수 있습니다.