[Python] 백준 - 13549 숨바꼭질 3

백준 - 13549 숨바꼭질 3

 

문제

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

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

입력

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

출력

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

 

 

문제해결방법 - 

 

 

1. 다익스트라 알고리즘과 BFS 알고리즘을 이용할 수 있다.

 

1) 다익스트라 

v[next] 에 방문을 처리할 때 (idx * 2) 인 경우, cost 와 동일하게 반영하고, 그 외의 경우 cost + 1 로 반영해준다.

2) BFS

0-1 BFS라고 하는데, 가중치가 0, 1 로만 나뉠 경우, BFS가 가능하다.가중치가 그 이상일 경우, v[next]가 한번 반영되어버리면 수정할 수 없기에 작동하지 않는 것 같다. (참고자료 1. https://deulee.tistory.com/11)

 

 

 

- 코드

1) 다익스트라 

import sys
from collections import deque
import heapq
sys.setrecursionlimit(10**8)
input = sys.stdin.readline

n, k = map(int, input().split())
INF = sys.maxsize
v = [INF for _ in range(100001)]

def dijk(idx):
	q = []
	heapq.heappush(q, (0, idx))
	v[idx] = 0
	while q:
		cost, idx = heapq.heappop(q)
		if k == idx:
			return v[k]
		if v[idx] < cost:
			continue
		for next in [idx-1, idx+1, idx*2]:
			if 0 <= next < 100001:
				if next != idx*2 and v[next] > cost+1:
					v[next] = cost+1
					heapq.heappush(q, (cost+1, next))
				elif next == idx*2 and v[next] > cost:
					v[next] = cost
					heapq.heappush(q, (cost, next))

print(dijk(n))

 

 

2) BFS

import sys
from collections import deque
import heapq
sys.setrecursionlimit(10**8)
input = sys.stdin.readline

n, k = map(int, input().split())
v = [-1 for _ in range(100001)]

def bfs(idx):
	q = deque()
	q.append(idx)
	v[idx] = 0
	while q:
		idx = q.popleft()
		print(idx)
		if idx == k:
			return v[idx]
		for next in [idx-1, idx+1, idx*2]:
			if 0 <= next < 100001 and v[next] == -1:
				if next == idx*2:
					v[next] = v[idx]
					q.appendleft(next)
				else:
					v[next] = v[idx]+1
					q.append(next)

print(bfs(n))
print(v[:k+2])