17071. 숨바꼭질 5 (Python)

 

17071번: 숨바꼭질 5

 

풀이

 시간 제한이 0.25초로 빡빡하기 때문에 일반적인 방문체크로는 정답을 구할 수 없다. 이때 필요한 것이 짝수초와 홀수초로 나누어 방문 체크를 하는 것이다.

 예를 들어 수빈이가 10의 위치에 2초에 도착했다고 가정해보자. 수빈이는 X-1이나 X+1을 이동할 수 있다. 즉, 10에서 왼쪽으로 한 번 이동하고 오른쪽으로 한 번 이동하는 방식으로 다시 같은 위치로 이동할 수 있다. 10의 위치에 2 + 2초, 2 + 4초, 2 + 6초, .... 와 같은 방식으로 도착할 수 있는 것이다. 만약 동생이 10의 위치에 6초가 걸려 도착했다면 둘은 6초에 10에서 만날 수 있음을 알 수 있다.

 

 그렇기 때문에 방문 체크는 짝수초와 홀수초로 나누어 해당 위치에 짝수초에 도착했는지 홀수초에 도착했는지를 체크한다.

visited[loc][0] : loc 위치에 짝수초가 걸려 도착했음을 의미
visited[loc][1] : loc 위치에 홀수초가 걸려 도착했음을 의미

 

 위와 같은 방법으로 방문 체크를 하면 시간 안에 수빈이와 동생이 몇 초에 만날 수 있는지를 구할 수 있다.

 

코드

LIMIT = 500_000

if __name__ == '__main__':
    N, K = map(int, input().split())

    # visited[loc][0] : loc 위치에 짝수초에 도착, visited[loc][1] : loc 위치에 홀수초에 도착
    visited = [[-1] * 2 for _ in range(LIMIT + 1)]

    if N == K:  # 시작부터 둘의 위치가 같을 경우 0 출력하고 종료
        print(0)
        exit()

    q = [N]
    time = 1
    K += time

    while True:
        if K > LIMIT:  # 동생이 500,000을 넘어서면 탐색 종료
            break

        nextQ = []

        for subin in q:
            for nextSubin in [subin + 1, subin - 1, subin * 2]:
                # 수빈이의 다음 위치가 범위 안에 있고 아직 도착한 적이 없는 위치라면
                if 0 <= nextSubin <= LIMIT and visited[nextSubin][time % 2] == -1:
                    nextQ.append(nextSubin)  # 새로운 큐에 위치를 넣어주고
                    visited[nextSubin][time % 2] = time  # 방문 체크를 해준다.

        # 동생의 위치 K가 짝수초 또는 홀수초에 도착한 적이 있다면
        # 현재 시간을 출력하고 시스템 종료
        if visited[K][time % 2] != -1:
            print(time)
            exit()

        time += 1
        K += time
        q = nextQ

    # 프로그램이 종료되지 않았다면 둘은 범위 내에서 만날 수 없음을 의미
    print(-1)