[백준12851/골드4] 숨바꼭질 2 - Python

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

 

숨바꼭질 3 문제는 이동 방법마다 초가 달라서 힙큐로 풀었는데 이 문제는 가중치가 같아서 덱으로 풀었다.

가장 빠른 시간으로 찾는 방법이 몇 가지 인지 구하는 문제가 해결하기 어려웠다.

visited 를 True / False로만 나눠서 풀면 해당 위치까지 몇가지의 수로 방문할 수 있는지 확인할 수 없었다.

 

일단 visited 배열을 만들고 -1로 초기화 한 후, 수빈이의 처음 위치 visited[N] 은 0초로 초기화했다.

visited[i] : i 위치에 도달하는데 최소 몇초가 걸리는지

그리고 bfs 탐색을 위한 queue 배열도 선언하고 (N까지 몇초에 왔는지, 위치N) 으로 시작했다.

q = deque([(0, N)])

bfs를 실행하면서 K에 도달했으면  조건 확인하고 cnt(도달까지 방법 수), result(최소 몇 초 걸리는지) 확인했다.

 

 

# 성공 코드

from collections import deque

N, K = map(int, input().split())
q = deque([(0, N)])
visited = [-1] * 100001
visited[N] = 0
result = float('inf')
cnt = 0

while q:
    t, c = q.popleft()
    
    # 수빈이를 찾았을 경우
    if c == K:
        # 처음 찾았으면 t가 최소 시간 -> 결과와 cnt 갱신
        if result == float('inf'):
            result = t
            cnt = 1
        
        # 결과와 같은 시간으로 도착했을 경우 -> cnt += 1
        elif result == t:
            cnt += 1
    
    # t가 이미 결과보다 오래 걸렸을 경우 -> continue
    if t >= result:
        continue
    
    # 다음 이동 경우의 수 세가지 순회
    for next in [c-1, c+1, c*2]:
        if 0 <= next < 100001:
            # 만약 처음 오는 곳이거나, 이미 가장 빠르게 갈 수 있는 시간과 같은 시간으로 도달할 경우
            # deque에 추가, 처음 오는 곳일 경우 visited 갱신
            if visited[next] == -1 or visited[next] == t+1:
                visited[next] = t+1
                q.append((t+1, next))

print(result)
print(cnt)