[백준] 13549 숨바꼭질

문제

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

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

입력

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

출력

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

 

접근 방법

처음는 0초에 가능한 수, 1초에 가능한 수, 2초에 가능한 수를 반복문을 통해 모두 구해, 완전탐색을 하여 시간 및 메모리 초과로 풀지 못했다.

 

다른 사람들의 질문을 보니 BFS나 다익스트라 알고리즘을 사용하였다는데, 전혀 감을 잡지 못해 코드를 찾아보았다.

 

생각보다 개념은 간단했다. 단순히 내가 했던 완전 탐색을 위한 리스트를 큐로 바꾸기만 하면 BFS가 되는 것이었다. BFS를 사용하여 구현했을 때 부족한 부분이 있었다. 바로 n-1과 n+1의 순서가 뒤 바뀌면 해결이 안되는 테스트 케이스가 있었기 때문이다.

 

따라서 해결책에 대해서 고민해본 결과 우선순위 큐를 사용하면 해결 되는 것을 알았다. 우선순위 큐의 정렬 기준을 해당 노드의 시간으로 하면 BFS의 단점을 보완할 수 있다. 그리고 실제 수행 시간도 거의 2배이상 단축 되었다.

 

소스 코드

파이썬

import sys
from queue import Queue

readline = sys.stdin.readline
INF = 100000

def main():
    N, K = map(int, readline().split())

    dist = [-1] * (INF + 1)
    q = Queue()
    dist[N] = 0

    q.put(N)  
    while q:
        n = q.get()
        if n == K:
            print(dist[n])
            break

        if (n * 2) <= INF and dist[n*2] == -1:
            dist[(n*2)] = dist[n]
            q.put(n*2)
        if (n - 1) <= INF and (n - 1) >= 0 and dist[n-1] == -1:
            dist[n-1] = dist[n] + 1
            q.put(n-1)
        if (n + 1) <= INF and dist[n+1] == -1:
            dist[n+1] = dist[n] + 1
            q.put(n+1)

if __name__ == "__main__":
    main()

import sys
import heapq

readline = sys.stdin.readline
INF = 100000


def main():
    N, K = map(int, readline().split())

    visited = [False] * (INF + 1)
    hq = []
    heapq.heappush(hq, [0, N])

    while hq:
        edge = heapq.heappop(hq)
        node = edge[1]
        dist = edge[0]

        if node == K:
            print(dist)
            break

        if node * 2 <= INF and visited[node*2] == False:
            visited[node*2] = True
            heapq.heappush(hq, [dist, node*2])
        if node + 1 <= INF and visited[node+1] == False:
            visited[node+1] = True
            heapq.heappush(hq, [dist+1, node+1])
        if node - 1 <= INF and node - 1 >= 0 and visited[node-1] == False:
            visited[node-1] = False
            heapq.heappush(hq, [dist+1, node-1])
if __name__ == "__main__":
    main()