[Python] 백준 13549번 - 숨바꼭질 3 (골드 5)

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

13549번: 숨바꼭질 3

 

혼자 힘으로 풀었는가? X

알고리즘 분류
 - 그래프 이론
 - 그래프 탐색
 - 너비 우선 탐색
 - 다익스트라
 - 0-1 너비 우선 탐색

 

문제

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

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

입력

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

출력

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

 

---

 

처음엔 DP로 풀어보려 했다.

 

그리고 실패했다. 코드를 어떻게 작성해야 할지 조차 감이 안 잡혔었다.

 

그다음 BFS로 풀어보려 했다.

 

코드는 작성했으나 틀렸다.

 

반례를 보고 좀 더 케이스를 생각해 보려고 질문게시판에 들어갔다가 정답코드를 우연히 봐버려서...

 

풀이방법을 한 번에 떠올려 버렸다.

 

테스트케이스만 보고 싶었는데 조금 억울하지만 보고나선 어렵지 않게 풀 수 있었다.

 

import sys
input = sys.stdin.readline

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

from collections import deque

dx = [-1, 1]

if n >= k:
    print(n-k)
else:
    visited = [-1] * (k*2)
    q = deque() #인접
    doubleQ = deque() #순간이동
    
    q.append(n)
    visited[n] = 0
    
    while q:
        now = q.popleft()
        doubleQ.append(now)
        while doubleQ:
            next = doubleQ.popleft()*2
            if next >= k*2:
                continue
            if visited[next] >= 0:
                continue
            
            visited[next] = visited[now]
            if next == k:
                print(visited[k])
                exit()
            doubleQ.append(next)
            q.append(next)
                
        for i in range(2):
            next = now + dx[i]
            if 0 <= next < k*2:
                if visited[next] >= 0:
                    continue
                visited[next] = visited[now]+1
                if next == k:
                    print(visited[k])
                    exit()
                q.append(next)

그냥 큐와 2배로 순간이동될 큐 두 가지를 관리한다.

 

그냥 큐에 넣은 수를 기본으로 2배 큐를 운용했다.

 

최단시간을 확인하기 위해선 우선 순간이동으로 이동할 수 있는 모든 거리를 파악하는 것이 중요하다.

 

그래서 순간이동 가능한 곳을 먼저 방문하고

일반 큐로 확인 가능한 -1, +1 은 나중에 방문한다.

 

처음 풀 때는 방문한 곳이 이미 값이 있을 경우

 

visited[next] = min(visited[now], visited[next])
or
visited[next] = min(visited[now], visited[next]+1)

이렇게 풀어야 하나 싶었는데 애초에 큐에 넣으면서 작업을 하면 가장 짧은 시간부터 확인을 하기 때문에

 

먼저 방문한 값이 당연히 최단 시간이 되기 때문에 위와 같이 풀 필요 없이 값이 있으면 continue를 해주었다.