[백분] 13913번 - 숨바꼭질 3 (파이썬)

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

# 숨바꼭질 3

from collections import deque


def bfs():
    q = deque()
    q.append(N)
    while q:
        now = q.popleft()
        if now == M:
            return visited[now]
        for k in [now-1, now+1, now*2]:
            nnow = k
            if 0 <= nnow < 1000001 and visited[nnow] == 0:
                if nnow == now*2 and now != 0:
                    visited[nnow] = visited[now]
                    q.appendleft(nnow)
                else:
                    visited[nnow] = visited[now] + 1
                    q.append(nnow)


N, M = map(int, input().split())
visited = [0] * 1000001
print(bfs())

 

BFS

1. deque인 q에 현재위치를 추가

2. q가 빌 때까지 q에서 now를 pop

  - q에 append (now+1, now-1은 append) (now*2는 우선순위가 높아서 appendleft)

  - 방문체크 (now+1, now-1은 +1) (now*2는 순간이동이므로 +0)

3. M에 도착시 return