[백준 1697] 숨바꼭질 (Python)

👩🏻‍💻문제링크

[백준 1697] 숨바꼭질 (Python)

✍️Idea Sketch

2021-07-28

1. 점 N의 범위 (0 ≤ N ≤ 100,000)

• visited는 크기가 100001인 배열

visited = [0]*100001  # 방법1
visited = [0 for i in range(100001)]  # 방법2

2. 소요 시간 카운트하는 방법

visited[i] = visited[v] + 1

3. 점 N 방문처리할 필요 없음

• N을 다시 방문하는 경로는 어차피 최단경로가 아님

def bfs(N, K, visited):
  queue = deque([N])
  visited[N] = 1  # 불필요

✍️소스코드

2021-07-28 156ms 통과

import sys
from collections import deque

N, K = map(int, sys.stdin.readline().split(' '))
visited = [0 for i in range(100001)]

def bfs(N, K, visited):
  queue = deque([N])
  while queue:
    v = queue.popleft()
    if v == K:
      return visited[K];
    for i in (v-1, v+1, v*2):
      if (-1<i<100001) and not visited[i]:
        queue.append(i)
        visited[i] = visited[v] + 1

print(bfs(N, K, visited))