[Gold IV] 숨바꼭질 4 - 13913

문제 링크

성능 요약

메모리: 41468 KB, 시간: 168 ms

분류

너비 우선 탐색, 그래프 이론, 그래프 탐색

문제 설명

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

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

입력

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

출력

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

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

풀이

아이디어

일단 되돌아가기 과정을 생각하지 말고 구현먼저 했다.
우선 문제 자체는 기본적인 "DP", "GRAPH" 형식을 띄고 있다.

함수의 역할은 다음과 같이 정의하였다.

기저사례를 먼저 설정한다.

1. 동생을 만난경우 : return depth
2. 리스트의 범위를 벗어난 경우 : return MAX

2번 조건의 경우 함수 호출 전에 미리 거르는 방식으로 한다.

코드

from collections import deque
MAX = 100001
n, k = map(int, input().split())
visited = [0] * MAX
reconsturct = [-1] * MAX

def solve(current):
    q = deque([current])
    visited[current] = 1
    while q:
        now = q.popleft()
        if now == k:
            return
        
        for c in [now * 2, now + 1, now - 1]:
            if 0 <= c < MAX and not visited[c]:
                q.append(c)
                visited[c] = visited[now] + 1
                reconsturct[c] = now

solve(n)
print(visited[k] - 1)

f = k
res = []
while f != -1:
    res.append(f)
    f = reconsturct[f]
print(*res[::-1])

BFS 방식으로 풀이하였고, reconstruct 리스트의 다음 값에 현재 위치를 저장한 뒤, 마지막에 while문에서 역추적하는 방식을 사용하였다.

문제를 여러 번 틀렸는데, 범위 지정 실수였다.

---

회고

얼마전에 공부했던 DP 역추적 테크닉을 이용하였다. 생각보다 추적하는 방식이 어렵지 않아 할만했다.