12851. 숨바꼭질 2 (Python)

12851번: 숨바꼭질 2

 

풀이

 bfs를 사용하여 답을 구할 수 있다. 현재 위치에서 +1, -1, *2를 해준 위치를 우선순위 큐에 넣고 시간이 빠른 것부터 큐에서 꺼내어 위의 과정을 반복한다. 방문 체크는 X위치에 도착한 시간을 사용한다. 만약 이전에 X 위치에 가장 빠른 시간 5초가 걸려 도착했는데 현재 다시 X에 도착한 시간이 6초라면 큐에 넣어주지 않는다. 하지만 4초에 도착했다면 가장 빠른 시간을 갱신하고 큐에 넣어 이동을 반복한다.

 

 한 가지 주의할 건 현재 위치에서 이동했을 때 100,000이 넘는 경우는 큐에 넣어줄 필요가 없다는 것이다. X * 2를 했을 때 100,000이 넘는 경우가 나올텐데 예를 들어 왜 넣어줄 필요가 없는지를 알아보자.

 현재 N이 50,001이고 K가 99,999라고 가정해보자. 먼저 *2를 해주면 100,002가 되고 99,999로 가기 위해서는 -1을 3번 해줘야 한다. 즉, 총 4초의 시간이 걸린다. 하지만 먼저 -1만큼 이동해서 50,000을 만들고 *2를 해주면 100,000이 된다. 여기에서 추가로 -1을 이동하면 99,999가 되는데 총 3초가 걸리는 것을 알 수 있다.

 결과적으로 먼저 *2를 통해서 100,000을 넘긴 후 -1을 통해 이동하는 것보다 -1을 통해 이동해서 *2를 했을 때 100,000을 넘기지 않는 값을 만든 후에 *2를 해주고 -1로 이동하는 것이 더 적은 시간이 걸린다. 그렇기 때문에 100,000이 넘는 경우는 굳이 큐에 넣어서 확인하지 않아도 된다.

 

코드

import heapq
INF = float('inf')
LIMIT = 100_000  # 위치의 최댓값

if __name__ == '__main__':
    N, K = map(int, input().split())
    q = []
    heapq.heappush(q, (0, N))  # N에서 0초에 시작
    
    # visited[X] : X 위치까지 이동하는데 걸린 최단 시간
    visited = [INF for _ in range(LIMIT + 1)]

    minTime = float('inf')  # N에서 K까지 가는데 걸린 최단 시간
    count = 0  # 최단 시간의 경우의 수

    while q:
        time, pos = heapq.heappop(q)  # pos까지 이동하는데 걸린 시간, 현재 위치

        if pos == K:  # K에 도착했을 때
            if time < minTime:  # 기존의 최단 시간보다 짧은 시간일 경우
                minTime = time  # 시간을 업데이트 하고
                count = 1  # 경우의 수는 다시 1부터 시작
            elif time == minTime:  # 같은 시간일 경우
                count += 1  # 경우의 수 1 증가
            continue

        if time > minTime:  # K에 도착하는데 걸린 시간보다 많은 시간이 걸렸을 경우에는 건너뛴다.
            continue

        for move in [1, -1, 2]:
            nextPos = pos  # 현재 위치에서 이동한 위치

            if move != 2:
                nextPos += move
            else:
                nextPos *= move

            # 다음 이동 위치가 0 이상 100,000 이하이고
            # nextPos에 도착하는 데 걸린 이전 최단 시간 이하일 경우에 큐에 넣어준다.
            if 0 <= nextPos <= LIMIT and time+1 <= visited[nextPos]:
                visited[nextPos] = time + 1
                heapq.heappush(q, (time+1, nextPos))

    print(minTime)
    print(count)