백준 13549번 : 숨바꼭질 3

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

13549번: 숨바꼭질 3

 

이 문제의 첫 인상은 그래프 탐색 문제처럼 보이지 않고 독특했다.

 

 0부터 100,000까지 점이 존재하고 수빈이와 동생이 이 점들 중 한 곳에 존재한다. 수빈이는 현재 위치를 기준으로 1만큼 뒤로 가거나 앞으로 갈 수 있지만 시간이 1초 소모된다. 또한 수빈이는 시간 소요없이 현재 위치에 2배가 되는 곳으로 순간이동 할 수 있다. 수빈이가 동생을 찾기 위해 소요되는 최소한의 시간을 구하는 문제다. 

 

 수빈이가 존재할 수 있는 위치는 0~100,000으로 한정돼있고 수빈이가 위치를 바꿀 수 있는 경우는 최대 3가지다. 그러니까 결국 하나의 위치 노드에는 3개의 위치 노드가 연결돼있다. BFS로 현재 위치와 연결된 위치를 하나하나 방문하고, 방문할때마다 그 위치까지 방문하는데 총 소요된 시간을 기록한다. 방문한 적 없는 위치를 방문하되 이미 방문한 위치더라도, 현재 위치에서 그 위치로 이동할 때 시간 소요가 더 적다면 그 위치에 도달할 때 걸리는 총 소요 시간을 갱신해준다. (단, 재방문은 하지 않는다.)

 

 그래프 탐색을 통해 모든 위치를 방문하고나서 동생이 있는 위치에 기록된 소요 시간을 출력하면 정답이다.

주의해야 할 것은 탐색 도중에 동생이 있는 위치에 도달하더라도 탐색을 종료하면 안된다. 왜냐하면 현재 도달한 경로말고 더 나중에(더 깊은 단계의) 탐색을 하던 중 시간 소모가 더 적은 경로를 발견할지도 모르기 때문이다.

탐색 과정에서 가장 먼저 동생에게 도달했다고 해서 그것이 그 위치까지 소요된 시간이 가장 적다는 걸 의미하는 것은 아니다.

import sys
from collections import deque
input = sys.stdin.readline

def bfs(s):
    queue = deque([s])
    d[s] = 0
    while queue:
        n = queue.popleft()
        r = [-1, 1, n]
        
        for i in range(3):
            pn = n+r[i]
            if 0 > pn or pn > 100000:
                continue

            cost = d[n]
            if i < 2:
                cost += 1

            if d[pn] < 0:
                queue.append(pn)
                d[pn] = cost
            elif cost < d[pn]:
                d[pn] = cost

num, k = map(int, input().split())
d = [-1]*100001

bfs(num)
print(d[k])