•
풀이
큐를 이용하여 값을 뽑아 사용하는 BFS의 기본 원리는 적용했지만, 최단 거리를 구하는 방법은 고민하다가 강의를 보고 정답을 얻었다.
각 노드(위치)를 조회할 때마다, 노드에 조회된 횟수를 누적시켜주는 것이다.
이 횟수로 해당 노드에 도달했던 방법의 갯수를 알 수 있다.
시작 위치에서 끝 위치로 갈수록 거치는 노드가 많아지며, 각 노드의 도달하는 방법도 그만큼 누적되는 원리를 이용한 것이다.
from collections import deque
def bfs(x, y):
# 처음 노드를 초기값으로 넣어준다.
queue = deque([(x,y)])
# 큐에 값이 들어있다면 계속 반복
while queue:
vx, vy = queue.popleft()
if vx == N-1 and vy == M-1:
break
if vx + 1 < N and MAP[vx+1][vy] == 1:
queue.append((vx+1,vy))
MAP[vx+1][vy] = MAP[vx][vy] + 1
if vx - 1 >= 0 and MAP[vx-1][vy] == 1:
queue.append((vx-1,vy))
MAP[vx-1][vy] = MAP[vx][vy] + 1
if vy + 1 < M and MAP[vx][vy+1] == 1:
queue.append((vx,vy+1))
MAP[vx][vy+1] = MAP[vx][vy] + 1
if vy - 1 >= 0 and MAP[vx][vy-1] == 1:
queue.append((vx,vy-1))
MAP[vx][vy-1] = MAP[vx][vy] + 1
N, M = map(int, input().split())
MAP = []
for _ in range(N):
MAP.append(list(map(int, input())))
bfs(0, 0)
print(MAP[N-1][M-1])
## 각 노드의 누적 조회 횟수 확인
# for i in range(N):
# for j in range(M):
# print(MAP[i][j], end='\t')
# print('')
Python
복사