[백준/Python] DFS/BFS - 1697번 숨바꼭질
👩🏻🏫 풀이
from collections import deque
def bfs(n):
queue = deque([n]) # deque([5])
while queue:
# 5,4,6,10,3,5,8,,,
x = queue.popleft()
if x == k:
print(dist[x])
break
for i in (x-1, x+1, x*2):
if 0 <= i <= 100000 and not dist[i]:
dist[i] = dist[x] + 1
queue.append(i)
# 수빈이가 있는 위치,동생이 있는 위치
n, k = map(int,input().split())
# [0,0,0,0,,,0]
dist = [0 for _ in range(100001)]
bfs(n)
- 가장 빠른 시간을 찾는 거라서 BFS를 생각했다.
for i in (x-1, x+1, x*2)
not dist[i]
if 0 <= 4, 6, 10 < 100000 and not dist[4,6,10]
if not dist[4,6,10]
:dist[4,6,10]
가 True가 아니라면- dist 변수의 초기값은 [0,0,0,0,....]으로 dist[i]는 언제나 False = 0
if not dist[i]
는 if문 조건을 만족시키는 것
dist[i] = dist[x] + 1
-dist[4,6,10]
= dist[5] + 1 = 1
Author And Source
이 문제에 관하여([백준/Python] DFS/BFS - 1697번 숨바꼭질), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@sugenius77/백준Python-DFSBFS-2178번-미로-탐색저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)