[골드 4] 13913번: 숨바꼭질 4

Original Source: 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는 정수이다.

출력

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

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

---

사고의 흐름

• 바로 전에 풀었던 문제와 비슷한데 이동 경로까지 출력해줘야 하네. List 하나 만들어서 이동 경로도 저장하면 되겠다.
• 원래는 Queue에 위치와 이동 경로 List를 같이 Append해주려고 했는데, 문제는 List가 Mutable한 객체여서 모든 탐색 경우마다 이동 경로가 추가된다. 이 방법은 안 되겠다.
• 그냥 전에 하던 것처럼 전체 점을 나타내는 List를 하나 더 만들어서 따로 이동 경로들을 저장해주면 되겠네.

 

• 크기가 100001인 List를 두 개 만드니까 메모리 초과가 뜬다. 이러면 움직임 횟수를 세지 말고 문자열로 이동 경로만 저장해서 BFS를 수행해야겠다.
• 움직인 횟수는 "".join(List) 를 사용해서 이동 경로를 하나의 문자열로 만든 다음 Length를 출력하면 되지 않을까?
• 근데 그러면 이동 경로 상의 점의 위치가 두 자릿수 이상이면 Length가 잘못 반영되겠네. 문자열을 공백 기준으로 List로 변환한 다음 List의 크기를 출력해야겠다.

 

• 그렇게 해도 메모리 초과가 난다. 아예 문자열로 List를 만들면 안 되나 보다.
• 정수 List를 만든 다음 각 칸에 움직이기 이전 위치의 값을 저장해 놓고 나중에 답을 출력할 때 위치를 타고 들어가면서 출력해주면 되겠다.

내가 작성한 소스코드

import sys
from collections import deque


def bfs(start, end, prev_point):
    q = deque()
    q.append(start)
    prev_point[start] = -2

    while q:
        cur_point = q.popleft()

        if cur_point == end:
            temp = [cur_point]
            while prev_point[cur_point] != -2:
                temp.append(prev_point[cur_point])
                cur_point = prev_point[cur_point]

            temp.reverse()

            print(len(temp)-1)
            for v in temp:
                print(v, end=" ")
            return

        if cur_point+1 <= 100000:
            if prev_point[cur_point+1] == -1:
                prev_point[cur_point+1] = cur_point
                q.append(cur_point+1)

        if cur_point-1 >= 0:
            if prev_point[cur_point-1] == -1:
                prev_point[cur_point-1] = cur_point
                q.append(cur_point-1)

        if cur_point*2 <= 100000:
            if prev_point[cur_point*2] == -1:
                prev_point[cur_point*2] = cur_point
                q.append(cur_point*2)


prev_point = [-1] * 100001
n, k = map(int, sys.stdin.readline().split())
bfs(n, k, prev_point)

남이 작성한 소스코드

hazung 님:
https://hazung.tistory.com/134

피드백

• bfs 함수 내부에서 현재 위치 + 1인 경우, 현재 위치 - 1인 경우, 현재 위치 * 2인 경우를 따로따로 작성했는데, 반복문을 사용해서 더 간결하게 바꿀 수 있다.

for i in (cur_point+1, cur_point-1, cur_point*2):
    if 0 <= i and i <= 100000:
        if prev_point[i] == -1:
            prev_point[i] = cur_point
                q.append(i)