숨바꼭질 2

백준 12851번: 숨바꼭질 2

아이디어

백준 1697번: 숨바꼭질 문제를 살짝 응용한 문제다. 가장 빠른 시간 내에 찾는 경우의 수를 구해야 한다. 큐에 집어넣는 조건을 바꿔줬다.
원래는 다음 위치에 저장된 값이 0일 때(방문한 적 없을 때) 큐에 집에넣었는데 이 문제에서는 다음 위치에 저장 된 값이 현재 위치에 저장된 값보다 클 때도(그 위치로 도달하는데 걸리는 시간이 같을 때를 의미한다. 다음 위치에 저장된 값이 현재 위치에 저장된 값보다 작다면 그곳으로 가는 더 효율적인 방법이 존재한다는 뜻이다.) 큐에 집에 넣었다.

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

N, K = map(int, input().split())
pos = [0] * 100001

def solve(start, end):
    q = deque()
    q.append(start)
    while q:
        x = q.popleft()
        if x == K:
            print(pos[x])
            break
        if x - 1 >= 0 and (pos[x - 1] == 0 or pos[x - 1] > pos[x]):
            pos[x - 1] = pos[x] + 1
            q.append(x - 1)
        if x + 1 <= 100000 and (pos[x + 1] == 0 or pos[x + 1] > pos[x]):
            pos[x + 1] = pos[x] + 1
            q.append(x + 1)
        if x * 2 <= 100000 and (pos[x * 2] == 0 or pos[x * 2] > pos[x]):
            pos[x * 2] = pos[x] + 1
            q.append(x * 2)
    ans = 1
    while q:
        x = q.popleft()
        if x == K:
            ans += 1
    print(ans)

solve(N, K)

여담

숨바꼭질 다풀어봐야지