[bfs/백준] 13913번 : 숨바꼭질 4

- 문제 : https://www.acmicpc.net/problem/13913

 

문제 이해 

- 이전 숨바꼭질 문제와 최소 이동시간 구하는 것은 동일한데, 최소 경로에 지나는 노드들을 출력하는 점이 다른 문제다. 

- 최소 시간은 동일해서 어렵지 않았지만, 경로를 어떻게 출력해야할지 잘 몰랐다. 

- 경로는 bfs의 특징을 이해해서 풀면 되는데, bfs를 수행하는 과정에서 현재 위치(부모 노드)를 다음 이동할 위치(자식 노드) 인덱스에 표시한다. (예 : check[자식노드] = 부모노드)

-> check를 이용하면 리프노드부터 위로 올라가면서 그 부모노드들을 찾을 수 있다.

풀이 로직 

- check 리스트는 수빈이가 다음으로 이동할 위치 인덱스에 현재 위치를 표시해주는 역할 (예 : check[자식노드] = 부모노드)

- move 함수는 이동 경로를 출력하는 함수이고, k부터 시작해 n까지 가는 경로를 진행하기 때문에 이를 거꾸로 바꿔서 출력한다.

- bfs를 진행하다가 k에 도착한 경우 최소 시간을 출력한 뒤 move()를 실행해 경로를 출력한다. 

- 아직 k에 도착하지 않았다면 x - 1, x + 1, 2 * x로 진행하면서 (1) 범위내에 있고, (2) 방문하지 않은 노드들로 탐색한다. 

- 노드를 방문처리한 뒤, queue에 넣는다. 이때 x가 부모이고 nx가 자식이므로 check[nx] = x 도 처리해준다. 

 

정답 풀이 

from collections import deque

def move(now):
    data = []
    temp = now
    for _ in range(visit[now] + 1):
        data.append(temp)
        temp = check[temp]        
    print(' '.join(map(str, data[::-1])))
    
    
def bfs():
    queue = deque()
    queue.append(n)
    while queue:
        x = queue.popleft()
        if x == k:
            print(visit[x])
            move(x)
            return 
        
        for nx in [x - 1, x + 1, 2 * x]:
            if 0 <= nx <= 10 **5 and not visit[nx]:
                visit[nx] = visit[x] + 1
                queue.append(nx)
                check[nx] = x
    
n, k = map(int, input().split())
number = 10 ** 5
visit = [0] * (number + 1)
check = [0] * (number + 1)
bfs()

 

 

참고 블로그 : https://data-flower.tistory.com/79