[파이썬] BOJ -13913 : 숨바꼭질4

링크

13913번: 숨바꼭질 4

문제

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

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

입력

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

출력

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

풀이

• 숨바꼭질1 문제의 로직에서 경로 추가만 하면 되는 문제라서 쉬워보였지만 처음에는 어떻게 경로를 찾아야 할지 헤맸다.
• 이 문제에 추가된 건 그 전에 탐색했던 경로를 저장하는 것이다. 트리로 생각하면 된다.
• result를 만들고 큐에 넣을 때, 미리 만들어놓은 path 배열에 result를 만들기 위해 썼던 부모 노드(num)을 저장해놓는다.
• 큐에서 하나를 pop할 때, 그게 K인지 검사한다.
• K이면, 임시로 temp에 저장해놓고, 배열 하나에 밀어넣은 다음, path 배열에서 부모를 찾는다.
• 끝까지 부모를 찾을 때까지 올라가면서 배열에 밀어 넣는다.
• 최초에 pop한 num의 범위까지 찾아도 되고, while문을 써서 temp와 N이 같아질 때까지 찾아도 된다.

  p.s : 정리하고 보니 for i in range(N,K-1,-1) ~~ return 까지는 필요없는 로직 같아 보인다.

코드

import sys
from collections import deque
N,K = map(int,sys.stdin.readline().split())

op_lst = [-1,1,2]

que = deque([[N,0]])
visited= [0 for _ in range(100001)]
path = [0 for _ in range(100001)]
def solve():
    if K<= N: # k가 n보다 작다면, 감소하는건 여기서 바로 처리.(n-k가 최소거리임.)
        print(N-K)
        for i in range(N,K-1,-1):
            print(i, end=" ")
        return
    while que:
        num,time = que.popleft()
        if num == K:
            print(time)
            p = [] # 정답 배열
            temp = num # 스위칭 할 temp
            for _ in range(visited[num]+1):
                p.append(temp)
                temp = path[temp]
            p.reverse()
            print(*p)
            break
        time+=1
        if num > 100000 or num < 0: # 시간 단축, num이 10만 넘어가면 굳이?, 0 미만은 위에서 거른다.
            continue
        for index in range(len(op_lst)):
            if index == 2:
                result = num * op_lst[index]
            else:
                result = num + op_lst[index]
            if 0 <= result < 100001 and visited[result]== 0:
                que.append([result,time])
                path[result]= num # path 배열에 현재 계산한 노드의 이전 노드를 설정
                visited[result]= visited[num]+1
solve()