(Python/🥇4)백준알고리즘 13913번: 숨바꼭질 4

 

문제 바로가기 

 

숨바꼭질 4

문제:

수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 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
from collections import deque

sys.stdin = open('/Users/song/Desktop/Python/Python/h.txt', 'r')
sys.setrecursionlimit(10*6)
n, m = map(int,sys.stdin.readline().split(" "))
dp = [0] * 100001 # 거리 저장
check = [0] * 100001 # 경로 저장
Q = deque([n])

# 지나온 경로 찾기 위한 dfs 시동 걸어야함.
def find(node):

    res = []
    for i in range(dp[node] + 1):
        res.append(node)
        node = check[node]
    print(*res[::-1])


while Q:
    node = Q.popleft()
    if node == m:
        dp_len = dp[node]
        print(dp[node])
        find(node)
        break
    for next_node in [node-1,node+1, 2*node]:
        if 0 <= next_node <= 100000 and not dp[next_node]:
            dp[next_node] = dp[node] + 1
            Q.append(next_node)
            check[next_node] = node

 

check라는 배열을 하나 더 써서

연결된 노선들을 저장해 둔다

예를들어 5> 10 > 9 > 18 >17 이면

5는 10을 가르키고

10은 9를 카르키고 ... 이런식으로