BFS를 활용한 풀이이다.
from collections import deque
def solution(maps):
x, y = 0, 0
n, m = len(maps), len(maps[0])
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
queue = deque()
queue.append((x, y))
while queue:
x, y = queue.popleft()
for di in range(4):
nx = x + dx[di]
ny = y + dy[di]
if nx < n and ny < m and nx >= 0 and ny >= 0:
if maps[nx][ny] != 0:
if maps[nx][ny] == 1:
maps[nx][ny] = maps[x][y] + 1
queue.append((nx, ny))
if maps[n-1][m-1] in [0, 1]:
return -1
else:
return maps[n-1][m-1]
이번 기회에 dfs, bfs 내용을 정리할 수 있었다. 특히, 이제는 왜 나는 'dfs 원툴'이다 / 'bfs 원툴'이다 라고들 이야기 하는지 깨달았다. 다만 각 알고리즘에 더욱 효율적인 알고리즘은 있으니 둘 다 자유자재로 사용할 줄 아는 것이 좋겠다.
문제를 딱 보면 이것이 DFS인지 BFS인지 딱 알아보는 안목이 생길 때까지 훈련이 필수적이겠다.