[BOJ/백준] 13549 숨바꼭질 3

# 13549 숨바꼭질 3
import collections
import sys
 
for _ in range(1000):
    start,end = map(int,input().split())
    dp = [-1]*100001
    dp[start] = 0
    dq = collections.deque()
    dq.append((start,0))
    if start == end:
        print(0)
    else:
        while True:
            x,time = dq.popleft()
            nx = 2*x
            while 0<nx <=100000:
                if dp[nx] == -1:
                    dp[nx] = time
                    dq.append((nx,time))
                nx = 2*nx
        
            if dp[end] != -1:
                break
            for nx in [x+1,x-1]:
                if 0<=nx<=100000:
                    if dp[nx] == -1:
                        dp[nx] = time + 1
                        dq.append((nx,time+1))
        
        print(dp[end])

첫 풀이 방식이다.  bfs처럼 풀었는데 단 조건은 두가지 경우를 나눠서 먼저했다. 먼저 해당위치에서 2배에 해당되는 것들만 먼저 방문을 해줬다. 왜냐하면 이동시간이 0초이기 때문이다. 그리고 난뒤 1초가 걸리는 +1,-1을 해주고 bfs 형식으로 풀어줬다.

start,end = map(int,input().split())
dp = [-1]*100001
dp[start] = 0
stack = [(start,0)]
if start == end:
    print(0)
else:
    while stack:
        new_stack = []
        for x,time in stack:
            for ind,nx in enumerate([2*x,x+1,x-1]):
                if 0<=nx<100001:
                    if dp[nx] == -1:
                        if ind == 0:
                            dp[nx] = time
                            new_stack.append((nx,time))
                        else:
                            dp[nx] = time +1
                            new_stack.append((nx,time+1))
        if dp[end] != -1:
            print(dp[end])
            break
        new_stack.sort(key=lambda x :(x[1]))
        stack = new_stack

ㅇ위와 똑같은 풀이이다. 하지만 여기서 달라진점은, 위에는 한개씩 진행한거에 반해 여기는 한단계씩 지금 내가 보유한 stack이 갈 수 있는 모든 곳을 다 넣어서, bfs를 돌린다는 것이다. 그리고 기준점은 시간이기때문에 시간을 기준으로 sort를 해주었다.

 

import heapq
start,end = map(int,input().split())
dp = [-1]*100001
dp[start] = 0
 
stack = []
heapq.heappush(stack,(0,start))
if start == end:
    print(0)
else:
    while stack:
        time,x = heapq.heappop(stack)
        for ind,nx in enumerate([2*x,x+1,x-1]):
            if 0<=nx<100001:
                if dp[nx] == -1:
                    if ind == 0:
                        dp[nx] = time
                        heapq.heappush(stack,(time,nx))
                    else:
                        dp[nx] = time +1
                        heapq.heappush(stack,(time+1,nx))
        if dp[end] != -1:
            print(dp[end])
            break

이 문제를 풀고보니 알고리즘 분류에 다익스트라가 있어서 그 방식으로 풀어본 코드이다. heapq를 이용한 방식이다.