[BOJ] 백준 1697번 숨바꼭질 - 파이썬(Python)

문제

수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다.

수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오.

입력

첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K가 주어진다. N과 K는 정수이다.

출력

수빈이가 동생을 찾는 가장 빠른 시간을 출력한다.

 

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

1697번: 숨바꼭질

 

💡 풀이 및 코드

from collections import deque

n, k = map(int, input().split())
graph = [-1] * 100001
dq = [1, -1, 2]

def bfs(start):
    queue = deque()
    queue.append(start)
    graph[start] = 0
    
    while queue:
        q = queue.popleft()
        
        for i in dq:
            nq = q * 2 if i == 2 else q + i
            if 0 <= nq <= 100000 and graph[nq] == -1:
                queue.append(nq)
                graph[nq] = graph[q] + 1
            if nq == k:
                return graph[nq]

print(bfs(n))

 

  처음 이 문제를 읽고 그래프 탐색 문제임을 알아채지 못했다. 힌트를 보고서야 정점 x가 정점 x-1, x+1, x*2와 연결되어 있는 형태임을 알고 BFS를 적용하였다. 또, 처음에는 방문처리가 필요하지 않다고 생각하였으나 방문처리를 해주지 않으면 중복 탐색에 발생하여 메모리 초과가 떴다.

문제를 보자마자 알고리즘을 떠올리기 위해선 연습이 더욱 필요할 것 같다!