[코딩테스트] 백준 숨바꼭질(1697) 파이썬(Python)

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

1697번: 숨바꼭질

from collections import deque

n, k = map(int, input().split())

q = deque()
q.append((n, 0))
visited = set()
visited.add(n)
while q:
    x, d = q.popleft()
    if x == k:
        break
    for next_x in [x-1, x+1, 2*x]:
        if next_x not in visited and 0 <= next_x <= 100000:
            visited.add(next_x)
            q.append([next_x, d+1])
print(d)

collections의 deque를 이용하여 bfs를 구현하였습니다.

 

q에 노드와 노드의 깊이(시간)을 저장하고 visited에 방문처리합니다.

그리고 bfs 알고리즘을 수행하는데 수빈이가 이동할 수 있는 x-1, x+1, 2*x를 차례로 확인합니다.

visited에 등록되어 있지 않고 조건 범위내에 위치한다면 방문처리를하고 q에 깊이(시간)을 하나 증가시켜서 저장합니다.

 

bfs의 종료조건은 x와 k가 동일할 때 종료합니다.

 

bfs가 종료되면 깊이(시간) d를 반환합니다.