💡 문제
수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다.
수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오.
입력
첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K가 주어진다. N과 K는 정수이다.
출력
첫째 줄에 수빈이가 동생을 찾는 가장 빠른 시간을 출력한다.
둘째 줄에 어떻게 이동해야 하는지 공백으로 구분해 출력한다.
💭 접근
1697번 숨바꼭질 문제와 유사한 문제지만 최단시간 뿐만 아니라 어떻게 이동했는지 이동 경로까지 출력해야하는 문제이다.
1697번 숨바꼭질 문제와 똑같이 x+1, x-1, x+x에 대해 최단시간을 구하기 위하여 BFS를 사용하여 최단시간을 구하는데, 이때 경로를 기록하며 나아간다. 아래 코드에선 path 배열을 사용하였는데, x가 이전 위치, nx가 현재 위치라고 하였을 때 path[nx] = x와 같이 현재 위치를 최단시간에 왔을 때 바로 직전의 위치를 저장하고, 목표위치에 도달하였을 때 다음과 같이 이를 순서대로 꺼내어 출력하면 된다.
if x == k:
ans = [k]
for _ in range(visited[x]):
tmp = ans[-1]
ans.append(path[tmp])
print(visited[x])
print(*ans[::-1])
break📒 코드
from collections import deque
def bfs(start):
visited[start] = 0
q = deque()
q.append(start)
while q:
x = q.popleft()
if x == k:
ans = [k]
for _ in range(visited[x]):
tmp = ans[-1]
ans.append(path[tmp])
print(visited[x])
print(*ans[::-1])
break
for nx in (x + 1, x - 1, x + x):
if 0 <= nx < 100001 and visited[nx] == -1:
visited[nx] = visited[x] + 1
path[nx] = x
q.append(nx)
n, k = map(int, input().split())
visited = [-1 for _ in range(100001)]
path = [0 for _ in range(100001)]
bfs(n)💭 후기
최단시간만을 구할 때는 쉽게 해결하였지만 경로를 어떻게 저장할 지 떠올리는 것이 까다로웠던 문제였다.
🔗 문제 출처
https://www.acmicpc.net/problem/13913
