최단거리를 구하는 문제라서 당연하게 bfs
로 접근하는데 그냥 단순하게 생각하고 풀면 아래의 반례에서 틀리게 된다. bfs
는 너비 우선 탐색으로 어떤 방향에서 접근하더라도 최단거리로 도착한 곳을 우선순위로 치게 된다. 이미 최단 거리로 돌아서 한 번 방문한 곳이라면 다시 방문하지는 않게 되는 것이다. 보통의 너비 우선 탐색 문제에서는 이게 통한다. 이미 최단 거리로 한 번 찍고 지나간 곳이라면 뒤늦게 그곳에 도달하는 경우는 이미 최단 거리가 아니게 되기 때문이다. 하지만 이 문제에서는 벽을 한 번 뚫고 지나갈 수 있다는 조건이 추가 되기 때문에 단순 너비 탐색으로는 이 문제를 풀 수 없게 된다.
6 4
0000
1110
0000
0111
1011
0000
위의 반례를 보면 (1, 2) 에 도달할 수 있는 경우가 2가지 존재한다.
bfs
나 다익스트라를 적용해서 풀 경우 최단거리를 우선으로 치기 때문에 visit[1][2]에는 무조건 벽을 뚫고 지나온 경우가 기록되고 돌아서 온 경우는 이 기록을 뛰어넘는 단거리가 될 수 없다. 하지만 (1, 2)에서 끝까지 도달하기 위해서는 반드시 벽을 한 번 더 뚫어야만 한다 하지만 최단거리로 온 현재의 경우 이미 벽을 한 번 뚫었기 때문에 한 번 더 뚫을 수 없고 결국 도달할 수 없다는 결론이 나 -1
을 리턴하게 된다. 하지만 벽을 뚫지 않고 돌아서 온 경우는 벽을 한 번 더 뚫을 수 있기 때문에 (1, 2)에 최단거리로 도착하지는 않았지만 최종적으로 도달 가능은 하다. 그렇다면 도달할 수 있는 최단거리가 존재하며 그것은 13
으로 리턴되어야 한다.
즉, 어떤 위치에 도달했을 때 '벽을 이미 한 번 뚫고 지나온 경우'와 '벽을 뚫지 않고 지나온 경우' 두 가지 정보가 다 기록되어 있어야 한다. 최종적으로 어떤 쪽이 더 빠르게 도달할 지는 현재 위치까지의 정보가 아니라 앞으로 벽의 존재 유무 등의 이후의 조건에 달려있기 때문이다. 하지만 보통 bfs
라면 현재 위치에 최단으로 도착했다면 끝까지도 최단으로 도착하게 되어있다.
- 칸마다 방문 체크 하나씩만 하는 방법으로는 풀 수 없습니다. 어떤 칸에 도달했을 때 나는 "아직 벽을 부술 수 있는 상태"일 수도 있고, "더 이상 벽을 부술 수 없는 상태"일 수도 있습니다. 큐에 그 상태를 넣은 것만으로 되는 것이 아닙니다. 당장 이 지점까지 어떻게든 최단으로 오는 길만 구했다고 해서, 그 이후의 여정도 최적으로 만들 수 있는 건 아닙니다. 구체적인 예시로는 다음과 같은 것들이 있습니다.
- 현재 칸까지 벽을 안 부수고 최단으로 올 수 있었다고 가정해봅시다. 현재 지점에서 목표 지점까지 가는 데에, 벽을 한 개 부수고 가는 것이 안 부수고 가는 것보다 최적이 나온다고 해봅시다. 그렇다면 지금 내가 벽을 더 부술 수 있는 상태라는 사실을 알고 있어야만 할 것입니다.
- 벽을 안 부수고도 현재 칸까지 도달이 가능하지만, 벽을 부수고 오는 것이 더 짧다고 가정해봅시다. 현재 지점에서 목표 지점까지 가려면 무조건 벽을 한 개 부숴야만 된다고 해봅시다. 비록 현재 칸까지는 벽을 부수고 오는 것이 최적이었지만, 이 상태로는 끝에 아예 도달을 못 하죠? 현재 칸까지는 더 멀더라도 벽을 안 부수고 와야, 끝에 도달이 가능합니다
틀렸습니다
import sys
from collections import deque
input = sys.stdin.readline
def bfs(i, j):
queue.append((i, j, False))
visit = [[0] * M for _ in range(N)]
visit[i][j] = 1
while queue:
si, sj, flag = queue.popleft()
for di, dj in ((1, 0), (0, 1), (-1, 0), (0, -1)):
ni, nj = si + di, sj + dj
if -1 < ni < N and -1 < nj < M and not visit[ni][nj]:
visit[ni][nj] = visit[si][sj] + 1
if not arr[ni][nj]:
queue.append((ni, nj, flag))
elif not flag and arr[ni][nj]:
queue.append((ni, nj, True))
if (si, sj) == (N-1, M-1):
return visit[si][sj]
return -1
N, M = map(int, input().split())
arr = [list(map(int, input().strip())) for _ in range(N)]
queue = deque()
print(bfs(0, 0))
import sys
from collections import deque
input = sys.stdin.readline
def dfs(y, x, cnt, flag):
global res
if res < cnt:
return
if (x, y) == (M-1, N-1):
res = cnt
return
for dx, dy in ((0, 1), (1, 0), (-1, 0), (1, 0)):
nx, ny = x + dx, y + dy
if -1 < nx < M and -1 < ny < N and visit[ny][nx] == 0:
visit[ny][nx] = 1
if arr[ny][nx] and not flag:
dfs(ny, nx, cnt+1, True)
elif arr[ny][nx] == 0:
dfs(ny, nx, cnt+1, flag)
visit[ny][nx] = 0
N, M = map(int, input().split())
arr = [list(map(int, input().strip())) for _ in range(N)]
visit = [[0] * M for _ in range(N)]
# stack = deque()
res = 1e9
dfs(0, 0, 1, False)
if res == 1e9:
res = -1
print(res)
1 1
0
이라는 반례 때문에 100%에서 에러 뜬다
import sys
from collections import deque
input = sys.stdin.readline
N, M = map(int, input().split())
arr = [list(map(int, input().strip())) for _ in range(N)]
visit = [[[0, 0] for _ in range(M)] for _ in range(N)]
queue = deque([(0, 0, 0)])
res = -1
while queue:
r, c, wall = queue.popleft()
if (r, c) == (N-1, M-1):
res = visit[r][c][wall] + 1
break
for dr, dc in ((-1, 0), (1, 0), (0, 1), (0, -1)):
nr, nc = r + dr, c + dc
if -1 < nr < N and -1 < nc < M and not visit[nr][nc][wall]:
if not wall and arr[nr][nc]:
visit[nr][nc][1] = visit[r][c][wall] + 1
queue.append((nr, nc, 1))
elif not arr[nr][nc]:
visit[nr][nc][wall] = visit[r][c][wall] + 1
queue.append((nr, nc, wall))
print(res)