[BOJ] 13549.숨바꼭질 3 (Python)

 

13549번: 숨바꼭질 3

이 문제는 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초인지 구하는 문제입니다.

수빈이의 시작 위치는 N, 동생 위치는 K, 수빈이가 이동한 위치는 X로 주어집니다.

수빈이가 걷는다면 1초 후 X-1 또는 X+1의 위치로 이동합니다.

수빈이가 순간이동한다면 0초 후 X*2의 위치로 이동합니다.

 

수빈이와 동생이 존재할 수 있는 최대 위치는 100000이므로 그것에 1을 더해 limit로 지정합니다.

이 limit는 수빈이의 다음 이동 위치를 제한하는 용도로 사용됩니다.

수빈이의 이동시간을 관리하기 위해 time 리스트를 생성합니다.

이 때, 방문하지 않은 X점에 대해 확인하기 위해 -1로 초기화합니다.

동생의 위치로 갈 때 순간이동이 가장 가까이 다가갈 수 있으므로 먼저 수행되어야 합니다.

그러므로 deque의 맨 처음 위치로 넣어주며 진행하도록 조정합니다.

 

이와 같은 방식으로 문제를 풀면 다음과 같습니다.

# 숨바꼭질 3
from collections import deque

def solution(N, K) :
    limit = 100001 # 최대로 주어지는 점 + 1
    time = [-1] * limit # 시간 저장을 위한 리스트
    time[N] = 0
    d = [2, -1, 1]

    q = deque()
    q.append(N)

    while q :
        X = q.popleft()
        if X == K :
            return time[X]
        for i in range(3) :
            if i == 0 : # 수빈이가 순간이동하는 경우
                nx = X * d[i]
                if 0 < nx < limit and time[nx] == -1:
                    time[nx] = time[X]
                    q.appendleft(nx)
            else : # 수빈이가 걷는 경우
                nx = X + d[i]
                if 0 <= nx < limit and time[nx] == -1 :
                    time[nx] = time[X] + 1
                    q.append(nx)

if __name__=="__main__" :
    N, K = map(int, input().split()) # 수빈이 위치, 동생 위치
    print(solution(N, K))