백준 1697 파이썬 : 숨바꼭질

https://www.acmicpc.net/problem/1697

1697번: 숨바꼭질

< 소스 코드 >

from collections import deque

def bfs(n,k):
  q = deque([n])
  while q:
    x = q.popleft()
    # 그냥 먼저 k에 도달하면 제일 작은 수.
    if x == k:
      print(dist[x])
      break
    ## for 문 작성법
    for nx in (x-1, x+1,x*2):
      ## nx 의 범위 체크, 이미 nx 에 도달한 경우 제외
      if 0 <= nx <= MAX and not dist[nx]:
        dist[nx] += dist[x] + 1
        q.append(nx)

n, k = map(int,input().split())
## 문제 지시사항의 최대 수를 체크할 것
MAX = 10 ** 5
##
dist = [0] * (MAX+1)
bfs(n,k)

문제 조건을 유의해 읽어야하거늘... MAX 를 4*k 로 했다가 틀렸다.

BFS 문제인데, 먼저 nx 에 도달하면 후에 nx 에 도달하는 경우를 아예 제외시킨다.

먼저 도달하면 당연히 그때껏 번째 수(?)도 최소가 된다.

원래 나는 for 문을 저렇게 쓸 생각을 못하고 각 경우 그대로 썼다가 코드가 라푼젤 머리길이만큼 길었으니..

파이썬은 for 문은 참 versatile 한 듯.