[13913] 숨바꼭질 4 - Python

/* 문제 */
수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다.
수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오.

동생을 찾을 수 있는 가장 빠른 시간과 이동 순서를 출력하는 문제다. 최단거리 문제이므로 bfs로 풀었다.

 

 처음에는 이동 순서를 저장하기 위해 visited 딕셔너리를 선언해 각 위치에 도달하기 위한 이동 순서를 리스트로 저장했다.

# 메모리 초과 코드
from collections import deque
n, k = map(int, input().split())
visited = {}
queue = deque([n])
visited[n] = [n]
while queue:
    v = queue.popleft()
    if v == k:
        print(len(visited[v]) - 1)
        print(' '.join(map(str,visited[v])))
        exit()
    for next_node in [v-1, v+1, v*2]:
        if 0 <= next_node <= 100000 and next_node not in visited.keys():
            visited[next_node] = visited[v][:]
            visited[next_node].append(next_node)
            queue.append(next_node)

그러나 이 코드는 메모리 초과가 났다. 모든 위치에 대해 리스트를 저장해야 하기 때문에 메모리가 불필요하게 사용됐던 것이다.

위 코드를 살펴보면 각 위치의 이동 순서를 저장할 때, 이전 위치의 이동 순서에 자기 자신을 더하는 과정을 반복하고 있다. 또한 bfs 알고리즘에 맞게 한 번 방문한 위치는 다시 방문하지 않는다. 즉 각 위치는 한 번만 업데이트 되며, 그 때 필요한 정보는 이전 노드의 정보 뿐이다. 따라서 visited에는 이 노드에 방문하기 전 어떤 노드를 방문했는지만 저장하고, 이후에 역추적하면 같은 결과를 얻을 수 있는 것이다.

 

# 정답 코드
from collections import deque

def check(visited, v, n):
    move = [v]
    now = v
    while now != n:
        move.append(visited[now])
        now = visited[now]
    print(len(move)-1)
    print(' '.join(map(str, move[::-1])))

def bfs(visited, n):
    queue = deque([n])
    visited[n] = n
    while queue:
        v = queue.popleft()
        if v == k:
            check(visited, v, n)
            return
        for next_node in [v-1, v+1, v*2]:
            if 0 <= next_node <= 100000 and visited[next_node] == -1:
                visited[next_node] = v  # 직전 방문 노드
                queue.append(next_node)

n, k = map(int, input().split())
visited = [-1 for _ in range(100001)]
bfs(visited, n)

위 코드에서는 visited를 딕셔너리가 아니라 리스트로 선언한다. 아직 방문하지 않은 노드는 -1로, 방문한 노드는 이전 노드의 위치를 저장한다. 

큐에서 꺼낸 위치가 동생의 위치와 같다면 check함수를 호출하고 탐색을 종료한다. check함수에서는 visited의 값을 기반으로 이전에 방문한 노드들을 역추적해 출력한다.