[白俊]2178:迷宮を探る
質問する
https://www.acmicpc.net/problem/2178
こうぞう
現在位置の4方向を決定
位置が範囲内であるかどうかを確認する条件
すべての条件が通過し、値が1の場合に移動します.
移動時に迷路値を1増加
次に、移動座標
最短パス
値を更新して最短パスをナビゲートできる理由
Queueへの追加()
つまり
이동한 좌표를 기준으로 또 상하좌우로 이동を作るという意味です!(追加しないという意味ではすでにアクセスしているので値は1ではないので、移動した座標によって上下左右に移動しません!!
に答える
from collections import deque
N, M = map(int, input().split())
miro = []
for _ in range(N):
miro.append(list(map(int, input())))
# miro : [[1, 0, 1, 1, 1, 1], [1, 0, 1, 0, 1, 0], [1, 0, 1, 0, 1, 1], [1, 1, 1, 0, 1, 1]
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
visited = [[False for _ in range(M)] for _ in range(N)]
def bfs(x, y):
queue = deque()
queue.append((x, y))
num = 1
while queue:
x, y = queue.popleft()
num = miro[x][y]
# for i in miro[x][y]: # k의 인접노드 for문 : 인접노드를 돈다기 보단, 상하좌우 -> 1이면 queue에 append
# if visited[i] == False:
# queue.append(i)
# visited[i] = True
for i in range(4):
a, b = x + dx[i], y + dy[i] # a, b는 이동할 경우의 점의 좌표
if 0 <= a <= N-1 and 0 <= b <= M-1:
if miro[a][b] == 1: # 이미 그 전에 방문했던 곳은 값이 갱신되어 있고 1이 아님! (그래서 최소경로 구할 수 있음)
queue.append((a,b))
miro[a][b] = num + 1
return miro[N-1][M-1]
print(bfs(0,0))Reference
この問題について([白俊]2178:迷宮を探る), 我々は、より多くの情報をここで見つけました https://velog.io/@letsbebrave/백준-2178-미로-탐색テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol