Python) 1697번 숨바꼭질

난이도 : 실버1
유형 : BFS
카테고리 : 백준 온라인 저지
날짜 : 2022-02-18

문제 풀이

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  # 불필요

전체 코드

import sys
from collections import deque
 
N, K = map(int, sys.stdin.readline().split(' '))
visit = [0 for i in range(100001)]
 
def bfs(N, K, visited):
  queue = deque([N])
  while queue:
    v = queue.popleft()
    if v == K:
      return visit[K];
    for i in (v-1, v+1, v*2):
      if (-1<i<100001) and not visit[i]:
        queue.append(i)
        visit[i] = visit[v] + 1
 
print(bfs(N, K, visit))