[백준] # 13913. 숨바꼭질 4 (파이썬)

문제 링크

 

https://www.acmicpc.net/problem/13913

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는 정수이다.

 

출력

 

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

둘째 줄에 어떻게 이동해야 하는지 공백으로 구분해 출력한다.

 

IDEA

 

현재 위치까지 왔을 때 걸린 시간을 기록하는 배열(time)과 이전 위치를 기록하는 배열(move)을 생성한다. queue를 생성하여 bfs를 활용하여 (x-1, x+1, x*2) 만큼 이동해보면서 time과 move 배열을 업데이트 해준다. 현 위치가 목적지에 도달할 경우 move배열을 활용하여 이전 위치를 출력해준다.

 

CODE

 

# 13913. 숨바꼭질 4 - 골드 4
# bfs 사용
from collections import deque
n,k = map(int,input().split())
time = [0] * 100001     # 현재위치까지 왔을 때 걸린 시간을 기록
move = [0] * 100001     # 이전 위치를 기록
q = deque([n])
if n >= k:
    print(n-k)
    for i in range(n,k-1,-1):
        print(i,end = " ")
else:
    while q:
        x = q.popleft()
        if x == k:
            temp = []
            temp_x = x
            print(time[x])
            for _ in range(time[x]+1):
                temp.append(temp_x)
                temp_x = move[temp_x]
            print(" ".join(map(str,temp[::-1])))
            break
        for i in (x-1,x+1,2*x):
            if 0 <= i <= 100000 and time[i] == 0:   # 방문하지 않았을 때
                move[i] = x
                time[i] = time[x] + 1
                q.append(i)

 

사용 알고리즘

 

BFS

 

풀이 평

 

꽤 어려웠다. 이전 위치를 저장할 생각도 못했다 ㅠ  블로그를 참고하여 풀었다.