BOJ: #13549. 숨바꼭질 3

문제

#13549. 숨바꼭질 3

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

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

---

접근 방식

실버 1 문제인 #1697. 숨바꼭질과의 차이점은 수빈이가 순간이동을 할 때 걸리는 시간이 1초에서 0초로 바뀌었다는 것이다.
즉, 한 번의 행동에 동일한 시간이 소요되는것이 아니다.

따라서 해당 문제는 다익스트라 알고리즘으로 접근하였다.

def solution(subin_x: int, sister_x: int) -> int:
	dist = [float("inf")] * 100_001
	dist[subin_x] = 0
	pq = [(0, subin_x)]
	while pq:
		d, x = heappop(pq)
		if x == sister_x: return dist[sister_x]
		if d > dist[x]: continue
		for nx, cost in [(x - 1, 1), (x + 1, 1), (x * 2, 0)]:
			if nx > 100_000 or nx < 0: continue
			nd = d + cost
			if nd < dist[nx]:
				dist[nx] = nd
				heappush(pq, (nd, nx))
	return dist[sister_x]

heapq를 사용하여 최소힙에 위치 및 이동 횟수 정보를 넣어주었고, 위치가 100,000을 넘어가게 되면 continue 하였다.
그 후 거리 배열(이동 횟수 배열)에서 동생의 위치에 해당하는 인덱스의 값을 리턴해주었다.

다른 방식

문제을 다 푼 다음 알고리즘 분류를 확인해보니 0-1 너비 우선 탐색이라는 항목이 보였다. 그래서 너비 우선 탐색을 활용하여 풀어보기로 했다.

0-1 너비 우선 탐색

간선 가중치가 0 또는 1인 그래프에서 최단거리를 $O(V+E)$에 구하는 알고리즘.
다익스트라보다 더 빠르고, 구현도 단순하다.

0-1 너비 우선 탐색에서 0과 1은 각각 다음과 같이 해석이 가능하다.

• 0: 우선순위 높음
• 1: 우선순위 낮음

일반적인 BFS는 큐를 하나만 쓰는데 어떻게 다익스트라처럼 동작할까?

0-1 BFS에서는 덱(deque)을 사용한다.

• 간선 가중치가 0 -> deque의 앞쪽에 넣음 (빨리 탐색)
• 간선 가중치가 1 -> deque의 뒤쪽에 넣음 (나중에 탐색)

위 아이디어를 가지고 코드를 구현해보면 다음과 같다.

def solution_with_BFS(subin_x: int, sister_x: int) -> int:
	dist = [float("inf")] * 100_001
	dist[subin_x] = 0
	queue = deque([(subin_x, 0)])
	while queue:
		x, d = queue.popleft()
		if x == sister_x: return d
		for nx, cost in [(x - 1, 1), (x + 1, 1), (x * 2, 0)]:
			if nx > 100_000 or nx < 0: continue
			if dist[x] + cost < dist[nx]:
				if cost == 0: queue.appendleft((nx, d))
				else: queue.append((nx, d + 1))
				dist[nx] = dist[x] + cost

만약 가중치(cost)가 0이라면 appendleft()를 통해 deque의 앞쪽에 넣고, 그렇지 않다면 원래 BFS 방식대로 append()를 통해 뒤쪽에 넣게 된다.
위 방식으로 우선순위를 정해줄 수 있다.

알고리즘	메모리	시간
Dijkstra	113680KB	184ms
0-1 BFS	113548KB	124ms

대략 60ms 차이가 나는 것을 알 수 있다.