[백준 BOJ] 13549 숨바꼭질3 (Python)

13549번: 숨바꼭질 3 (acmicpc.net)

13549번: 숨바꼭질 3

두 가지 방법으로 풀 수 있다!

1. 다익스트라 (Heap, Priority Queue 활용)
2. 0-1 BFS (Deque 활용)

다익스트라는 힙에서 다음 위치를 꺼낼 때 우선순위를 고려해야하므로, (걸린 시간, 위치)의 형태로 삽입을 하게 된다.

 

이에 반해 BFS는 가중치(수빈이가 다음 위치로 가는 데 걸리는 시간, 여기서는 0과 1뿐이다.)에 따라 큐에 삽입하는 위치를 달리해서 위의 '우선순위' 기능을 대신한다. 이때 가중치가 0이면 우선순위가 높으므로 큐의 앞에, 1이면 큐의 뒤에 삽입한다.

 

from heapq import heappush, heappop


def dijkstra(x):
    q = []		# 다익스트라는 항상 동일하다! 힙이나 우선순위큐를 사용
    heappush(q, (0, x))	# (가중치, 노드)의 형태로 삽입

    field = [-1] * MAX	# 가중치(여기서는 걸린 시간) 행렬 초기화
    field[x] = 0	# 시작 위치의 가중치는 항상 0

    while q:
        time, cx = heappop(q)
        if cx == k:
            return field[cx]

        for i in range(3): # 이동할 수 있는 위치(X - 1, X + 1, X * 2) 세 개 고려
            if i == 0:
                nx = cx - 1
            elif i == 1:
                nx = cx + 1
            else:
                nx = cx * 2

            if not 0 <= nx < MAX:			   # 범위를 벗어나거나
                continue
            if field[nx] != -1 and field[nx] <= field[cx]: # 이미 방문했고,
                continue				   # 지금까지 걸린 시간보다 적으면 갱신 안 함

            if i < 2:			# 한 칸씩 이동한 경우 1초
                heappush(q, (time + 1, nx))
                field[nx] = time + 1
            else:			# 순간이동한 경우 0초
                heappush(q, (time, nx))
                field[nx] = time


n, k = map(int, input().split())
MAX = 100001
print(dijkstra(n))

 

from collections import deque


def bfs(x):
    q = deque([x])		# 다익스트라와 달리 가중치(시간) 없음!
    time = [-1] * MAX		# 중복방문을 위한 가중치행렬
    time[x] = 0

    while q:
        cx = q.popleft()
        if cx == k:
            return time[cx]

        for i in range(3):
            if i == 0:
                nx = cx - 1
            elif i == 1:
                nx = cx + 1
            else:
                nx = cx * 2

            if not 0 <= nx < MAX:	# 조건 검사 역시 다익스트라와 동일
                continue
            if time[nx] != -1 and time[nx] <= time[cx]:
                continue

            if i < 2:			# 한 칸씩 이동하는 경우 큐 뒤에 삽입
                q.append(nx)
                time[nx] = time[cx] + 1
            else:			# 순간이동하는 경우 큐 앞에 삽입
                q.appendleft(nx)
                time[nx] = time[cx]


n, k = map(int, input().split())
MAX = 100001
print(bfs(n))

 

시간은 둘 다 비슷한데 BFS가 40ms 정도 빠르게 나왔다!! ♪(´▽｀)