[백준/python] 12851번 : 숨바꼭질 2

문제

수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다.

수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 그리고, 가장 빠른 시간으로 찾는 방법이 몇 가지 인지 구하는 프로그램을 작성하시오.

 

입력

첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K가 주어진다. N과 K는 정수이다.

 

출력

첫째 줄에 수빈이가 동생을 찾는 가장 빠른 시간을 출력한다.

둘째 줄에는 가장 빠른 시간으로 수빈이가 동생을 찾는 방법의 수를 출력한다.

 

정답

import sys
input = sys.stdin.readline

N, K = map(int, input().split())

if K == N:      # 둘이 같은 위치에 있을 때
    print(0)
    print(1)
elif K < N :    # 동생이 뒤에 있을 때
    print(N-K)
    print(1)

else:
    visited = [0 for _ in range(100001)]
    queue = [N]
    time = 0

    while queue:
        time += 1
        next_queue = []
        for n in queue:
            if (n >= 0 and n <= 100000) and (visited[n] == 0 or visited[n] == time):
                next_queue.extend([n*2, n-1, n+1])
                visited[n] = time

        if next_queue.count(K) > 0:
            print(time) 
            print(next_queue.count(K))
            break
        
        queue = next_queue

---

• visited : visited에 가능한 위치의 모든 숫자를 0으로 셋팅한다.
• queue : queue에는 같은 레벨에 있는 숫자들이 들어갈 예정이고 레벨이 바뀔 때마다 queue의 값도 바뀐다.
• time : bfs 기반이기 때문에 time은 시간 즉, 레벨을 의미한다.
• next_queue : next_queue는 다음 레벨의 숫자들이 저장되어 있다가 현재 레벨의 숫자들을 다 탐색한 후에 queue에 저장된다.

queue에 있는 모든 숫자를 하나씩 돌면서

위치의 범위 안에 해당하면서, 한번도 방문한 적이 없거나 현재 레벨에서 방문했다면

next_queue에 현재 위치에서 갈 수 있는 위치의 숫자들을 추가하고

현재 레벨에서 방문했음을 표시하기 위해 visited[n]에 현재 레벨 time을 저장한다.

 

queue를 다 돈 후 next_queue에 내가 가야할 K가 1개 이상 있다면

time과 next_queue에 있는 K의 개수를 출력하고 멈춘다.