BOJ 13913. 숨바꼭질 4 (파이썬 Python)

Solved.ac 기준 🥇골드 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

5 17

예제 출력 1

4

5 4 8 16 17

 

대충 이렇게 나와야 하는데 앞에 가장 빠른 시간은 원래 하던대로 하면 된다. 근데, 뒤에 어떻게 이동하는게 막막했다. 그래서 일단 리스트 파서 무작정 넣어봤다.

음,,,이건 아니라고 생각했다..

 

그렇다면 어떻게 해야 할까,,? 이번에도 로직을 찾아보았다..ㅠㅠㅠㅠㅠ (언제 내 머리로 찾을지..슬프다..)

참 대단하신것 같다.. 따로 MAX 리스트를 만들어서 x값을 넣고, 재귀를 돌리며 원래 시작했던 값이 나올때까지 출력하면 되는거였다.

 

말이 이해가 잘 안갈수도 있는데,

 

일단 제일 빨리 가는 시간을 구할때, 거기다가 move_to 라고 따로 만든 리스트에 (초기화를 0으로 MAX_INDEX + 1 만큼해줬다) 같이 본래의 값을 넣어준다.

for nx in (x-1, x+1, x*2):
        if 0 <= nx <= MAX_INDEX and board[nx] == MAX_INDEX:
            q.append(nx)
            board[nx] = board[x] + 1 
            move_to[nx] = x # 이거다

그러니까 이동한 곳에 현재의 인덱스 수를 넣어준것이다. 이렇게 차곡차곡 넣어주고,

 

def move(n,m):
    if n != m:
        move(n,move_to[m])
    print(m, end=' ')

이렇게 n,k값을 매개변수로 넣어주고 난 뒤에, 뒤에서부터 쭉쭉 가는거다. 근데 재귀라 다시 앞에서부터 출력되는것이다. (사실 이건 잘 모르겠다) 이렇게 풀어나갔다. 

 

전체코드

# 숨바꼭질 4
from collections import deque
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)
n,k = map(int,input().split())
MAX_INDEX = 100000
board = [MAX_INDEX] * (MAX_INDEX+1)
move_to = [0] * (MAX_INDEX + 1)
q = deque()
q.append(n)
board[n] = 0
while q:
    x = q.popleft()
    if x == k:
        break
    for nx in (x-1, x+1, x*2):
        if 0 <= nx <= MAX_INDEX and board[nx] == MAX_INDEX:
            q.append(nx)
            board[nx] = board[x] + 1
            move_to[nx] = x

def move(n,m):
    if n != m:
        move(n,move_to[m])
    print(m, end=' ')

print(board[k])
move(n,k)

참,,하면 할 수록 벽이 느껴지는 알고리즘의 세상이다..