[백준 13913] 숨바꼭질 4 (with Python / BFS)

문제링크

https://www.acmicpc.net/problem/13913

13913번: 숨바꼭질 4

문제설명

 

문제

수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다.

수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오.

입력

첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K가 주어진다. N과 K는 정수이다.

출력

첫째 줄에 수빈이가 동생을 찾는 가장 빠른 시간을 출력한다.

둘째 줄에 어떻게 이동해야 하는지 공백으로 구분해 출력한다.

예제 입력 1 복사

5 17

예제 출력 1 복사

4
5 10 9 18 17

예제 입력 2 복사

5 17

예제 출력 2 복사

4
5 4 8 16 17

 

문제풀이

처음 시도한 방법 (틀린 코드)

from collections import deque

N, K = map(int, input().split())
M = 100000
dist = [[-1, []] for _ in range(M+1)]

def BFS(start):
    queue = deque([start])
    dist[start][0] = 0
    dist[start][1].append(start)

    while queue:
        cur = queue.popleft()

        if cur == K:
            print(dist[K][0])
            print(*dist[K][1])

        for next in (cur-1, cur+1, cur*2):
            if 0 <= next <= M:
                if dist[next][0] == -1:                
                    queue.append(next)
                    dist[next][0] = dist[cur][0] + 1
                    for i in dist[cur][1]:
                        dist[next][1].append(i)
                    dist[next][1].append(next)

BFS(N)

 

이렇게 시도했었는데 당연히 각 노드까지의 전체경로를 매번 저장하려고 하니 메모리 초과가 나는건 당연한 일이었다.

 

해결방법

- 각 노드까지 경로 중 직전 노드정보만 저장하자!

 => 그래서 목표노드에 도달하면 역 추적을 통해 경로를 알 수 있다.

코드

from collections import deque

N, K = map(int, input().split())
M = 100000
dist = [[-1, -1] for i in range(M+1)] # 첫번째 인덱스의 값으로 최소시간 저장, 두번째 인덱스 값으로는 직전노드 정보 저장
path = []

def BFS(start):
    queue = deque([start])
    dist[start][0] = 0

    while queue:
        cur = queue.popleft()

        # 목표 노드에 도달하면 dist[cur][1](직전 노드정보)에 있는 원소들을 조회하며 하나씩 역으로 조회하기
        if cur == K:
            print(dist[K][0])
            while cur != -1:
                path.append(cur)
                cur = dist[cur][1]
            for i in range(len(path)-1, -1, -1):
                print(path[i], end=' ')

        for next in (cur-1, cur+1, cur*2):
            if 0 <= next <= M:
                # 방문안한 노드라면 
                if dist[next][0] == -1:                
                    queue.append(next)
                    dist[next][0] = dist[cur][0] + 1
                    dist[next][1] = cur	# 직전 노드 정보 저장

BFS(N)


# 최단시간 출력하고
# 이동 경로까지 출력