[백준] 13913 - 숨바꼭질 4

1. 문제

13913번: 숨바꼭질 4

2. 개요

1697번: 숨바꼭질

1697 숨바꼭질 문제와 똑같은데 경로까지 출력해야하는 문제.

3. 코드 및 추가내용

bfs를 이용하여 풀었따.

import queue
import sys

N, K = map(int, sys.stdin.readline().split())
route = [K]

if N == K:
    print(0)
    print(*route)
    
else:
    q = queue.Queue()
    visited = [0 for i in range(100001)]
    parents = [-1 for i in range(100001)]
    parents[N] = N
    q.put(N)

    while q and visited[K] == 0:
        now = q.get()
        dests = [now-1, now+1, now*2]

        for dest in dests:
            if dest < 0 or dest > 100000:
                continue
            if visited[dest] != 0 and visited[dest] <= visited[now] + 1:
                continue
        
            visited[dest] = visited[now] + 1
            parents[dest] = now
            q.put(dest)

    print(visited[K])

    while True:
        route.append(parents[K])
        if parents[K] == N:
            break
        K = parents[K]
        
    route.reverse()
    
    
    print(*route)

전체적인 코드는 1697과 같다고 보면 된다.

큐에서 빼낸 값을 확인하여 해당 위치의 visited배열 값이 현재 위치의 값 +1 보다 크지 않다면 값을 1만큼 늘려주고(경과시간) 다음 탐색 위치를 탐색하여 큐에 넣는것을 반복한다.

추가된것은 경로인데, 따로 route배열과 parents배열을 만든다.

경로의 도착점은 미리 넣어두고, 시작점의 parents의 값은 자기 자신으로 한다.

visited의 값을 늘려 줄 때, parents의 값을 전의 위치로 잡아준다.

도착점에 도착했다면, 도착점의 위치에서부터 parents를 조회하며 역순으로 경로를 탐색,

route배열에 넣어주고 뒤집어 출력한다.