💻 13549: 숨바꼭질

문제 소개 🧐

수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이의 위치가 N, 동생의 위치가 K일 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간을 구하는 문제이다.

입력 📝

첫째 줄에 수빈이의 위치 N과 동생의 위치 K가 주어진다. (0 ≤ N, K ≤ 100,000)

출력 📤

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

제한 ❌

  • 시간: 2초
  • 메모리: 512MB

나의 풀이: 피보나치 수열의 발견! 🎉

Idea

이 문제에서 순간이동(2*X)은 0초가 걸리므로, 일반적인 BFS로는 최단 시간을 보장하기 어렵다고 판단했다. 따라서 가중치가 다른 간선이 있는 그래프에서의 최단 경로를 찾는 문제로 보고, 다익스트라 알고리즘을 사용했다.

나의 풀이에서는 heapq를 사용하여 우선순위 큐를 구현함으로써 다익스트라 알고리즘과 유사하게 동작하도록 했다. 큐에 (시간, 위치)를 저장하고, 시간이 적게 걸리는 경로를 우선적으로 탐색하여 최단 시간을 찾는다.

Code

import sys
import heapq

n, k = map(int, sys.stdin.readline().split())

def get_min_walk():
    dp = [float('inf')] * 100001
    dp[n] = 0
    q = []
    q.append([dp[n], n])
    while dp[k] == float('inf') and q:
        sec, loc = heapq.heappop(q)

        for i in range(3):
            n_sec, n_loc = -1, -1

            if i == 0:  # 순간이동
                n_loc = loc*2
                n_sec = sec
            elif i == 1 :  # +1 로 걷기
                n_loc = loc +1
                n_sec = sec +1
            else:  # -1로 걷기
                n_loc = loc -1
                n_sec = sec +1
            
            if not (0 <= n_loc < 100001):  # index 범위 벗어남
                continue

            if dp[n_loc] != float('inf'):  # 이미 들른 곳이면 continue
                continue

            if dp[n_loc] > n_sec:
                dp[n_loc] = n_sec
                heapq.heappush(q, [n_sec, n_loc])

    return dp[k]

if n >= k:
    print(n-k)
else:
    print(get_min_walk())

Result

성공! ✅

배운 점 및 느낀 점 ✍️

  • 나는 heapq를 이용한 다익스트라 방식으로 구현했는데. 0-1 BFS 를 활용해 풀수도 있다고 한다. 0-1 BFS는 덱(deque)을 사용하여 0초 이동은 덱의 앞에, 1초 이동은 덱의 뒤에 넣어 우선순위를 부여하는 방식인데, 다음엔 그 방법으로 풀어봐야겠다.