[BOJ] (DP, BFS) 13549번 숨바꼭질3 ??

코드 순서를.. x*2를 맨 앞에 놔야 통과한다

x*2를 마지막에 넣었을 때랑 결과값이 다르게 나온다.

질문 검색을 해보니, 그냥 우연히 이렇게 된것.

 

x*2를 0초마다 갈 수 있다는 말을 다른말로 하면, 가중치가 0인 간선이 있다는 것이다.

bfs는 모든 간선의 가중치가 동일해야 쓸 수 있음

 

0-1BFS라는 방법이 있는데, 이건 가중치가 0 인 간선에 연결된 정점은 큐의 맨 뒤가 아닌 맨 앞에 넣는 방법이다. appendleft등을 이용해서.

다른 방법으로는, x*2를 별도의 간선으로 생각하지 않고, +1이나 -1에 의한 좌표를 큐에 넣을 때 그 좌표의 2의 거듭제곱 배인 좌표들을 전부 큐에 넣는 방법이다., 

 

 

from collections import deque
import sys

input = sys.stdin.readline
SIZE = 100002
n, k = map(int, input().split())

def solve():
    if n >= k:
        return n-k

    dp = [-1] * SIZE
    dp[n] = 0
    
    q = deque()
    q.append((n, 0))

    while q:
        now, cnt = q.popleft()

        #x*2
        next_pos = now*2
        if 0<=next_pos<SIZE and dp[next_pos]<0:
            if next_pos == k:
                return cnt
            dp[next_pos] = cnt
            q.append((next_pos, cnt))
        
        #x-1
        next_pos = now-1
        if 0<=next_pos<SIZE and dp[next_pos]<0:
            if next_pos == k:
                return cnt+1
            dp[next_pos] = cnt+1
            q.append((next_pos, cnt+1))
        
        #x+1
        next_pos = now+1
        if 0<=next_pos<SIZE and dp[next_pos]<0:
            if next_pos == k:
                return cnt+1
            dp[next_pos] = cnt+1
            q.append((next_pos, cnt+1))
        

    
print(solve())

 

https://www.acmicpc.net/problem/13549