바킹독 BFS 강의 연습 문제
bfs 알고리즘은 알겠는데 이걸 조금만 꼬아도 어떻게 답을 도출하는지를 생각하기가 힘들다. 문제를 많이 풀면서 여러 유형에 익숙해지는 게 답인 것 같다.
이번 문제는 n * m 크기 미로의 (1, 1) 칸에서 시작해서 (n, m) 칸까지 가는 경로의 길이를 구하는 것이 목적이었다. 그 길이를 도대체 언제 재야 하나 여러 방법을 시도하다가 결국 강의의 힌트를 참고했다.
popleft()를 하고 나서 그 칸을 중심으로 인접한 칸을 확인하는 방식이니까 이번에 append()할 칸이 popleft()한 칸보다 1만큼 더 이동했다고 보면 되는 거였다. 즉 새로 append()하는 칸은 popleft()했던 칸 + 1을 넣어주어 길이 값을 갖도록 board를 수정하고, 마지막에 (n, m) 칸의 수를 출력한다.
from collections import deque
n, m = map(int, input().split())
board = []
for _ in range(n) :
board.append(list(map(int, input())))
dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]
q = deque()
q.append((0, 0))
while q:
x, y = q.popleft()
for i in range(4) :
nx = x + dx[i]
ny = y + dy[i]
if nx < 0 or nx >= n or ny < 0 or ny >= m :
continue
if board[nx][ny] == 1 :
board[nx][ny] = board[x][y] + 1
q.append((nx, ny))
print(board[n - 1][m - 1])
