[Baekjoon/Python] 1697번: 숨바꼭질(BFS)

# Baekjoon 1697번: 숨바꼭질
import sys
from collections import deque 
input = sys.stdin.readline

N, K = map(int, input().split())
visited = [0] * 2000002

def BFS(pos):
    queue = deque()
    queue.append(pos)
    visited[N] = 1
    
    while queue:
        c = queue.popleft()
        
        if c == K:
            return visited[c]-1
            
        for i in (c-1, c+1, 2*c):
            if visited[i] == 0 and 0 <= i < 1000001:
                queue.append(i)
                visited[i] = visited[c]+1

print(BFS(N))

이 문제는 BFS 알고리즘 문제이다. 처음 이 문제를 접하고 백트래킹처럼 그래프를 만든 후 이미 방문한 점이면 return 하는 방식으로 재귀함수를 만들며 해결하려 했는데, 재귀가 많이 반복돼서 while문을 이용한 BFS로 해결하게 되었다.

먼저, visited 배열과 queue를 만든 후 처음 시작점인 N을 queue에 추가한 뒤 방문했다는 것을 표시한다. 그 다음 while문을 이용해 queue의 원소를 추출해서 K와 비교하고, 다를 경우에는 다른 점으로 이동하도록 한다. 다른 점은 다시 queue의 원소로 추가한 뒤 visited 배열에 이전 점에서 1을 더한 값을 넣는다.