[백준/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

좋은 웹페이지 즐겨찾기