#문제링크
https://www.acmicpc.net/problem/13549
13549번: 숨바꼭질 3
수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일
www.acmicpc.net
#나의풀이
import sys
from collections import deque
if __name__=="__main__":
N, K = map(int, sys.stdin.readline().split())
max_num = 100001
DP = [2147000000] * (max_num)
queue = deque()
queue.append(N)
DP[N] = 0
while(queue):
tmp = queue.popleft()
if 0 <= tmp-1 < max_num and DP[tmp-1] > DP[tmp]+1:
DP[tmp-1] = min(DP[tmp-1], DP[tmp]+1)
queue.append(tmp-1)
if 0 <= tmp+1 < max_num and DP[tmp+1] > DP[tmp]+1:
DP[tmp+1] = DP[tmp]+1
queue.append(tmp+1)
if 0 <= tmp*2 < max_num and DP[tmp*2] > DP[tmp]:
DP[tmp*2] = DP[tmp]
queue.append(tmp*2)
if tmp-1 == K or tmp*2 == K:
print(DP[K])
break#해설
이 문제도 다익스트라로 구분되는데 DP로 풀었다.
시작점을 큐에 넣고 꺼내 이동할수 있는 3가지 방법으로 수를 이동시키고 조건에 맞다면 큐에 넣고 반복하여 돌려주었다.
수를 발견하면 출력해주고 종료시켜주었다.