백준 13913번 숨바꼭질 4 | python | bfs

문제

링크

풀이

숨바꼭질 시리즈를 깨는 맛이 있다.

이번 문제는 수빈이가 동생을 찾는 가장 빠른 시간을 구하는 것은 동일하나, 그 경로까지 출력해야한다.

따라서 경로 파악을 위해 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. 동생을 찾은 시점에 경로를 찾는 과정

이 되겠다