[BOJ] 13549번 - 숨바꼭질3 (Python)

🛠️ 문제 🛠️

---

🗒️ 설명 🗒️

어제 공부한 다익스트라 알고리즘을 연습해보았다.

다익스트라 알고리즘과 BFS 2가지 방식으로 풀어보았다. (코드는 아래에)

1. 다익스트라 알고리즘을 이용한 풀이

1. 수빈이의 위치를 시작 정점으로 둔다.
2. 현재 위치 i에 +1, -1 *2 한 위치에 대해 저장되어 있는 시간 times[k]와 도달한 시간(times[i] + 1 또는 times[i])을 비교하여 도달한 시간이 더 작으면 times[k]를 갱신한다.
3. heap이 빌 때까지 2번 과정을 반복한다. 

이때, 주의할 점은 가중치가 없지만 가중치로 생각한 값은 도달한 시간으로 times의 값이다.

만약 이를 times를 도착 정점의 개수만큼만 만들면 올바른 값을 도출하지 못할 것이다.

위의 문제에서 주어진 예시만 봐도 17에 도착하는 시간을 구해야하는데 18에 대한 값도 필요한 것을 알 수 있다.

 

2. BFS를 이용한 풀이

이 문제에서 그래프는 가중치가 없는 그래프로 정점을 탐색하여 가장 빠르게 동생의 위치로 도착하면 된다.

즉, 가중치가 없는 그래프에서 최단 거리를 구할 때 BFS를 사용하여 구할 수 있다.

 

위의 풀이가 BFS, 아래의 풀이가 다익스트라를 이용한 것으로 다익스트라 보다 BFS 풀이의 시간이 더 빠른 것을 볼 수 있다.

그 이유에 대해 생각해보면 다익스트라 알고리즘을 이용할 때 heap 자료구조를 사용했는데 이는 삽입 동작이 발생할 때마다 주어진 가중치에 대해 갱신이 이뤄져야한다. 반면에 BFS에서는 queue를 사용하여 삽입 과정에 추가적인 동작이 없으므로 BFS를 이용한 풀이가 더 빠르게 나올 수 있다.

---

🍀 풀이 🍀

1. 다익스트라 알고리즘을 이용한 풀이

import sys
import heapq

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

def dijkstra(start, end) :
    times = [sys.maxsize] * 100001
    heap = []
    
    times[start] = 0
    heapq.heappush(heap, [times[start], start])
    
    while heap :
        t, v = heapq.heappop(heap)
        for n in [v + 1, v - 1, v * 2] :
            if n >= 0 and n <= 100000 :
                if n == v * 2 and times[n] > t :
                    times[n] = t
                    heapq.heappush(heap, [times[n], n])
                elif times[n] > t + 1 :
                    times[n] = t + 1
                    heapq.heappush(heap, [times[n], n])
    print(times[end])
dijkstra(n, k)

2. BFS를 이용한 풀이

import sys
from collections import deque

n, k = map(int, sys.stdin.readline().split())
                
def BFS(start, end) :
    times = [sys.maxsize] * 100001
    queue = deque()
    
    times[start] = 0
    queue.append(start)
    
    while queue :
        current = queue.popleft()
        
        for n in [current + 1, current - 1, current * 2] :
            if n >= 0 and n <= 100000 :
                if n == current * 2 and times[n] > times[current] :
                    times[n] = times[current]
                    queue.append(n)
                elif times[n] > times[current] + 1 :
                    times[n] = times[current] + 1
                    queue.append(n)
    print(times[end])
BFS(n, k)