백준 13913번 파이썬 문제풀이(BFS - 숨바꼭질 4)

---

위 문제는 https://ji-gwang.tistory.com/298 문제에서 방문기록을 추가로 출력하라는 문제이다. 그러면 여기서 접근할 수 있는 방법이 방문기록을 찾아나가면서 방문기록을 어딘가에 저장하면 된다는 것이다. 

여기서 생각해볼 수 있는 상황이 있다. 위에 2번째 계층 트리 4, 6, 10 에 5를 저장하고 3번째 계층 트리에서 3, 5, 8 에 4, 그리고 5, 7, 12 에 6 마지막으로 9, 11, 20 에 10을 추가하면 된다.

이런식으로 방문기록을 추가해놓고 마지막에는 그 방문기록을 역으로 찾아 나가면서 출력하면 된다.  예를들어 시작점이 5 이고 목적지가 12라고 하자. 위의 그림을 보면 12에 저장되어있는 6을 찾고 그리고 그 6 값을 가지고 거슬러 올라가면서 6에 저장되어있는 5를 찾으면 된다는 것이다.

 

from collections import deque


def bfs(start):
    queue = deque([[start, 0]])
    while queue:

        x, cnt = queue.popleft()

        # find 함수 (자기 노드의 부모를 찾아가는 함수)
        if x == K:
            arr = []
            while x != parent_node[x]:  # 만약 자신의 부모가 최상위 부모가 아니라면 반복문돌기
                arr.append(parent_node[x])  # 우선 부모의 길을 저장해주고
                x = parent_node[x]  # 부모를 저장해준다.

            return cnt, [K] + arr  # 본인의 노드까지 리스트에 넣어 반환

        for i in range(3):
            if i != 2:
                nx = x + dx[i]
            else:
                nx = x * dx[i]

            # nx가 범위를 벗어나지 않고 방문을 안했고 출발지가 아니라면
            if 0 <= nx <= 100000 and not visited[nx] and nx != start:
                visited[nx] = True
                queue.append([nx, cnt + 1])
                parent_node[nx] = x


N, K = map(int, input().split())

dx = [-1, 1, 2]  # 이동방향 처리
visited = [False] * 100001  # 방문처리할 리스트
parent_node = [i for i in range(100001)]  # 자신의 부모노드를 저장할 리스트

cnt, arr = bfs(N)
print(cnt)
print(*arr[::-1]) #반대로 출력