[BOJ] 숨바꼭질 3 (no.13549)

문제

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

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

입력

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

출력

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

숨바꼭질 문제들 중독성 있다... 끝까지 풀고 자련다

🤔 생각

• 간선에 가중치가 생겨버린 문제다.

• 이러면 BFS 말고도 다익스트라로도 가능해진다. 물론 난 BFS 재탕을 할거지만 구조를 좀 바꾸긴 해야한다.

• 0,1,1 가중치를 가진 세개의 간선이 있다면 뭘 먼저 가봐야겠는가? 당연히 0인 것을 먼저 선택해야 최단거리를 반환할 것이다.

• 즉,우선순위 큐(priority queue) 구조인 heap으로 풀면 된다.

• heapq 모듈을 써도 되긴 되지만, 그냥 먼저 넣어야 하는 노드의 조건문을 상단에 두면 그게 우선순위 큐나 다름없다.

여기서, 어차피 BFS는 먼저 도착하는 놈이 제일 짧은건데 왜 이렇게 해야하는가? 만약 1을 먼저 선택한다면 어떻게 되는데? 라는 의문이 들 수 있다.

• 가중치가 없는 문제였다면 맞는 논리다.
• 이 문제에서 우선순위를 두지 않고 한다면, 최단가중치가 아니라 최단레벨(깊이)을 도출하는 꼴이 된다.
• 큐는 FIFO(First-In-First-Out) 구조이므로, BFS는 큐에 같은 레벨 노드가 여럿 있더라도 먼저 나오는 놈이 먼저 타겟을 잡으면 그 노드가 답이 된다.
• 그러므로 우선적으로 고려해야 하는 0의 간선를 먼저 큐잉함으로써 가장 짧은 가중치 합을 가진 상태에서 타겟을 잡게 하는 것이다.

미래에 내가 헷갈릴 수 있을 것 같아서 열심히 정리했다...

📌 내 풀이

import sys
input = sys.stdin.readline

def main():

    def bfs(n,k):
        q = [(0,n)]
        cache = [False]*100001

        while q:
            tmp = []

            for cnt,x in q:
                if x == k: return cnt

                if x*2 <= 100000 and not cache[x*2]: 
                    cache[x*2] = True
                    tmp.append((cnt,x*2))
                if 0 <= x-1 and not cache[x-1]: 
                    cache[x-1] = True
                    tmp.append((cnt+1,x-1))
                if x+1 <= 100000 and not cache[x+1]: 
                    cache[x+1] = True
                    tmp.append((cnt+1,x+1))
                
            q = tmp

    n,k = map(int, input().split())
    print(bfs(n,k))


if __name__ == "__main__":
    sys.exit(main())

✔ 회고

• 가중치가 있는 BFS는 대부분 우선순위 큐일 확률이 높다.
• 다익스트라도 한번 재활하자!