정답 코드
from _collections import deque
dx, dy = [-1, 1, 0, 0], [0, 0, -1, 1]
n, m = map(int, input().split())
data = [list(map(int, input())) for _ in range(n)]
visited = [[[-1, -1] for _ in range(m)] for _ in range(n)]
def bfs():
q = deque()
q.append((0, 0, 0))
visited[0][0][0] = 1
while q:
pop_x, pop_y, flag = q.popleft()
for i in range(4):
nx, ny = pop_x + dx[i], pop_y + dy[i]
if 0 <= nx < n and 0 <= ny < m:
if data[nx][ny] == 0 and visited[nx][ny][flag] == -1:
visited[nx][ny][flag] = visited[pop_x][pop_y][flag] + 1
q.append((nx, ny, flag))
elif flag == 0 and data[nx][ny] == 1 and visited[nx][ny][1] == -1:
visited[nx][ny][1] = visited[pop_x][pop_y][flag] + 1
q.append((nx, ny, 1))
result1, result2 = visited[n-1][m-1][0], visited[n-1][m-1][1]
if result1 != -1 and result2 == -1:
print(result1)
elif result1 == -1 and result2 != -1:
print(result2)
else:
print(min(result1, result2))
bfs()
최단 거리를 구할 때 벽을 뚫은 상태냐, 아닌 상태냐에 따라 계산하는 방법을 생각해 내야 한다.
그러기 위해서는 bfs함수 안에 각각의 의미를 정확하게 알아야 한다.
pop_x, pop_y, flag = q.popleft() 는 무엇을 꺼내는 것일까?
- q에는 시작 지점부터 append해서, 순차적으로 뻗어나가는 현재 위치와 같은 것이다. 현재 위치가 뻗어나아가 도착지점까지 도달하면서 해당 지점까지의 최단 거리를 구할 수 있었던 것이다.
여기서 이 문제는 해당 지점이 벽을 뚫을 상태인지, 뚫지 않은 상태인지를 판별하기 위해 flag라는 상태 값을 추가해 주었다.
visited는 왜 3차원 배열로 만들었을까?
visited는 각 지점까지의 최단 거리를 저장하고 있다. 3차원으로 만든 이유는 벽을 뚫을 상태와 뚫지 않은 상태에서의 최단 거리를 저장하기 위해서였다.
Q1. 그럼 그냥 2차원 배열에다가 하면 어떤 문제가 있을까?
벽을 부술 때, 벽을 부수지 않은 쪽 visited에서 값을 더해줘야 하기 때문에 3차원 배열을 만들게 된 것이다.
그냥 2차원 배열로 하고, 깬 상태랑 깨지 않은 상태랑 값을 비교해서 더 작은 쪽을 넣어주면 어떤 문제가 생길까?