[Python] 숨바꼭질 - 백준 (BFS)

해당 글은 백준 1697번 문제 '숨바꼭질'을 다룬다.

문제

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

1697번: 숨바꼭질

 

설명

BFS로 x-1, x+1, 2*x의 경우로 이동했을 경우의 최소값을 업데이트하며 구한다.

이때 방문한 경우를 체크해야 메모리 초과 문제가 나타나지 않는다.

 

코드

from collections import deque
n, k = map(int, input().split())
max = 100000
def bfs(x):
    q = deque()
    q.append(x)
    visited[x] = True
    while q:
        x = q.popleft()
        if x == k:
            return
        if x-1 >= 0 and visited[x-1] == False:
            q.append(x-1)
            dist[x-1] = min(dist[x]+1, dist[x-1])
            visited[x-1]=True
        if x+1 <= max and visited[x+1] == False:
            q.append(x+1)
            dist[x+1] = min(dist[x]+1, dist[x+1])
            visited[x+1] = True
        if 2*x <= max and visited[2*x] == False:
            q.append(2*x)
            dist[2*x] = min(dist[x]+1, dist[2*x])
            visited[2*x] = True


dist = [100001]*(max+1)
visited = [False]*(max+1)
dist[n]=0

bfs(n)
print(dist[k])