숨바꼭질 시리즈를 깨는 맛이 있다.
이번 문제는 수빈이가 동생을 찾는 가장 빠른 시간을 구하는 것은 동일하나, 그 경로까지 출력해야한다.
따라서 경로 파악을 위해 visited 리스트와 같은 크기의 move 리스트를 만들어주었다. move의 인덱스는 현재 위치를 의미하는데, 이 때 현재 위치로 오기 전의 위치값을 배열에 채워준다. 즉 이전 방문 노드를 채운다고 생각하면 쉽다.
bfs 실행과정은 이전 숨바꼭질 시리즈의 과정과 동일하므로 생략하겠다.
from collections import deque
import sys
input = sys.stdin.readline
s, b = map(int, input().strip().split())
move = [0] * 200001 # 부모 노드 저장
visited = [0] * 200001 # 방문 여부 파악 및 sec 갱신
ans_sec = 100001 # 최종 빠른 시간 저장하는 변수
way = []
def bfs():
global ans_sec
global way
q = deque()
q.append(s)
move[s] = 0 # 이전 방문 노드를 채울거임. 근데 s는 초기 노드니까 이전 방문 노드 자체가 없으므로 0으로 초기화
while q:
x = q.popleft()
if x == b:
ans_sec = visited[x]
# 동생을 찾은 시점에 경로를 파악하 과정
cur_node = x
way.append(x)
while True:
if cur_node == s:
break
way.append(move[cur_node])
cur_node = move[cur_node]
print(ans_sec)
for w in way[::-1]:
print(w, end=" ")
break
arr = [x - 1, x + 1, x * 2]
for a in arr:
if 0 <= a <= 200000 and (visited[a] == 0):
move[a] = x #move 리스트에 이전 노드를 저장하는 과정
visited[a] = visited[x] + 1
q.append(a)
return ans_sec
bfs()
코드에서 보다시피 추가된 부분은
1. move 리스트에 이전 노드를 저장하는 과정
2. 동생을 찾은 시점에 경로를 찾는 과정
이 되겠다