[백준] 1697번 문제 (숨바꼭질) 파이썬(Python) 풀이

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

1697번: 숨바꼭질

from collections import deque
n, k = map(int, input().split())
visited = [False] * 100001
q = deque()
q.append([n, 0])

while q:
    pivot, d = q[0][0], q[0][1]
    if pivot == k:
        break
    q.popleft()
    visited[pivot] = True
    if pivot - 1 >= 0 and not visited[pivot - 1]:
        q.append([pivot - 1, d + 1])
    if pivot + 1 <= 100000 and not visited[pivot + 1]:
        q.append([pivot + 1, d + 1])
    if pivot * 2 <= 100000 and not visited[pivot * 2]:
        q.append([pivot * 2, d + 1])

print(q[0][1])

 

bfs문제이다.

큐에 시작점인 n과 카운트인 0을 리스트에([n, 0]) append 해준다.

그 후 bfs가 끝날때까지

경우의 수 3가지의 방법으로 탐색을 진행한다.