알고리즘 유형 : DP(Dynamic Programming)
풀이 참고 없이 스스로 풀었나요? : X
https://www.acmicpc.net/problem/13913
소스 코드(파이썬)
import sys
from collections import deque
input = sys.stdin.readline
N, K = map(int, input().split()
# 시간 리스트
count = [0 for _ in range(100001)]
# 직전 방문 노드 저장 (연결 리스트 개념과 비슷)
path = [0 for _ in range(100001)]
# 제너레이터 (-1, +1, *2 순회)
def move(n):
# 0은 2 곱해도 0
# 0에서 0으로 가는 경우는 이동이 일어난
# 경우가 아니기에 배제시켜줌
if n != 0:
yield n*2
yield n+1
yield n-1
def solution():
# BFS
q = deque()
q.append(N)
while q:
n = q.popleft()
if n == K:
break
for _n in move(n):
if 0 <= _n <= 100000 and count[_n] == 0:
count[_n] = count[n] + 1
# -n에 방문하기 직전의 노드인 n을 저장
# = 연결 정보를 저장
path[_n] = n
q.append(_n)
# K부터 시작해서 바로 직전 연결 노드를 연속적으로
# 탐색하여 최단경로 역추적
time = count[K]
root = [K]
tmp = K
for i in range(time):
tmp = path[tmp]
root.append(tmp)
print(time)
print(*root[::-1])
solution()
풀이 요약
- BFS에 역추적을 섞는 풀이이다.
-
우선 기본적인 토대는 BFS이다. N부터 시작하여 너비 우선 탐색하여 K까지의 최단 시간을 구한다.
이에 더하여 최단 경로까지 같이 구해줘야한다.
주의해야할 점은, count를 구하는 로직과 같이 path 메모이제이션 리스트를 만들고, 거기에
path[이전노드] + 현재 노드 문자열과 같은 방식은 메모리 초과가 발생한다.1부터 10만까지 1씩 더한 경로에 대해 생각해보면, 문자열의 길이가 공백을 제외하고 생각해도 10만(10만-1)/2이다.
이는 문자열말고 리스트에 append하는 식의 로직도 비슷한 이유로 MLE이 발생한다.
따라서, 연결 리스트와 비슷한 개념으로 최단 경로 역추적의 토대를 마련한다.
-
path 리스트를 100001 크기로 할당한다. path[idx]는 idx로 오기 직전의 수를 의미한다. 즉 바로 직전에 연결된 노드를 담고 있는 것이다. 따라서 BFS를 수행한 뒤 역추적할 때 K부터 거꾸로 처음 출발 노드까지 역으로 조회할 수 있다는 뜻이다.
path[idx]에 저장된 노드는 반드시 최단 경로상의 연결 노드이다. 너비 우선 탐색이기에 가장 먼저 도착한 노드에 대하여 할당한 값이 최단 값이고, 그 이후에 다시 변경되는 일은 없기 때문이다.
-
한편, BFS에서 인접 노드인 *2, -1, +1을 탐색할 때 주의할 점이 있다.
N = 0, K = 1인 테스트케이스를 생각해보자.
이 때 인접 노드는 *2, -1, +1이다.
0*2=0인데, count[_n] = count[n] + 1에 의해 count[0] = 1이 되버린다.
이 후 0+1=1에 대해, count[1] = count[0] + 1이 되어 count[1] = 2가 되버린다.
원래 0에서 0으로 가는 경우는 제자리이기 때문에 이동이 발생했다고 할 수 없는데, 0의 곱셈이 0이 되는 특성에 의해 예외적으로 이동한 경우로 취급되어 시간이 +1초가 되버리는 것이다.
따라서, 제너레이터에서 n이 0이 아닌 경우에만 n+2를 yield하는 것으로 해결해주자.
배운 점, 어려웠던 점
- 처음에 연결 리스트 개념과 비슷한 풀이가 아닌, 문자열 또는 리스트로 path를 이어붙여나가는 식으로 풀었다가 메모리 초과가 났는데 그 이유를 생각해내질 못해서 다른 사람 풀이를 참고했다.
- 이 문제처럼 연결 리스트와 유사한 방식으로 최단 경로를 역추적하는 아이디어가 되게 참신하다고 느꼈다. 유익한 경험이었다.
