백준 13549번 : 숨바꼭질 3 in Python

13549번: 숨바꼭질 3

 

www.acmicpc.net

이 문제는 이전의 숨바꼭질 문제에서 순간이동에 걸리는 시간이 1초가 아닌 0초인 경우 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지를 구하는 문제이다.

백준 1697번 : 숨바꼭질 in Python

1697번: 숨바꼭질 www.acmicpc.net 위 문제는 어떤 한 점에서 다른 한 점으로 가기 위해 걸리는 최단 시간을 구하는 문제로, 이동 방법에는 앞뒤로 한 칸 또는 그 점의 좌표만큼 앞으로 이동하는 방법이 있다. 만..

wanna-be-developer-yjh.tistory.com

이 문제는 기존의 숨바꼭질 문제와는 달리 순간이동에 걸리는 시간이 0초이기 때문에 BFS로 알고리즘을 구현할 때 순간이동을 별도로 구현할 필요가 있다.

즉, 처음 시작 위치가 a라고 하면, a*2^n ( n : 자연수 )에 해당하는 모든 위치를 0초인 순간에 방문할 수 있기 때문에 이를 우선 방문한 뒤 queue에 해당 위치를 모두 넣어야 한다. 단, 매번 다른 위치로 갈 때마다 이를 고려할 필요는 없다. 특히 a*2^n에 해당하는 위치에 간 경우 그 위치에 2의 거듭제곱을 곱한 위치는 이미 방문했기 때문에 a에 2의 거듭제곱을 곱한 경우가 아닌 경우에만 고려하면 될 것이다. 이는 queue에서 꺼낸 위치에 2를 곱한 위치를 방문했는지를 확인함으로써 알 수 있다.

이 밖의 나머지 구현은 기존의 숨바꼭질 문제와 유사하게 구현하면 된다.

이를 코드로 구현하면 다음과 같다.

from collections import deque
N, K = map(int, input().split())
# 각 위치를 처음 방문하기까지 걸리는 시간
# 초기값은 방문하지 않았음을 표시하기 위해 -1로 한다.
sec = [-1 for _ in range(200000)]
# 수빈이의 위치에 해당하는 원소 초기화
sec[N] = 0
queue = deque()
queue.append(N)
# BFS 구현
while queue:
    u = queue.popleft()
    # 동생의 위치에 도달한 경우 while loop을 빠져나온다.
    if u == K:
        break
    # 해당 위치에서 순간 이동하는 경우를 고려한다.
    temp = u*2
    # 해당 위치에 2의 거듭제곱을 곱한 위치를 방문하지 않은 경우에만 그 위치를 방문한다.
    while temp < 200000 and sec[temp] == -1:
        if sec[temp] == -1:
            sec[temp] = sec[u]
            queue.append(temp)
        temp *= 2
    if u < 199999 and sec[u+1] == -1:
        sec[u+1] = sec[u] + 1
        queue.append(u+1)
    if u > 0 and sec[u-1] == -1:
        sec[u-1] = sec[u] + 1
        queue.append(u-1)
print(sec[K])