🥚문제

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

• 그래프 이론
• 그래프 탐색
• 너비 우선 탐색

---

🥚입력/출력

---

🍳코드

import sys
from collections import deque
input = sys.stdin.readline

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

# time[x] = x까지오는데 걸린 시간 저장
# prev[x] = x에 오기 전 y 저장
def bfs():
    q = deque([N])
    time = [-1]*100001
    prev = [-1]*100001
    time[N] = 0
    prev[N] = None # 시작하는 N은 None으로 저장한다

    while q:
        x = q.popleft()
        # 도달
        if x == K:
            print(time[x])
            path = find_path(x, prev)
            print(' '.join(map(str, path)))
            return

        # X-1
        if 0 <= x-1 and time[x-1] == -1:
            time[x-1] = time[x] + 1
            prev[x-1] = x
            q.append(x-1)
        # X+1
        if x + 1 <= 100000 and time[x+1] == -1:
            time[x+1] = time[x] + 1
            prev[x+1] = x
            q.append(x+1)
        # 2*X
        if x*2 <= 100000 and time[x*2] == -1:
            time[x*2] = time[x] + 1
            prev[x*2] = x
            q.append(x*2)

def find_path(x, prev):
    # x까지 도달하는 데 거쳐온 위치들을 구한다
    path = []
    while True:
        if x is None:
            return reversed(path)
        path.append(x)
        x = prev[x]


# 함수 실행
bfs()

---

🧂아이디어

BFS

• 수빈이가 동생을 찾는 최소 시간과, 이동 경로를 출력해야하는 문제.

• 맨 처음에 제출한 코드는 deque에 (현재위치, 현재위치까지 오는 경로)형식으로 정보를 저장했는데, 시간초과가 발생했다.

• 따라서, 위치 x까지 오는 데 걸리는 최소 시간은 time[x]에 저장하고

• 위치 x까지 오기 전에 있었던 위치 y를 path[x] = y로 저장했다.

• 동생의 위치 K에 도달하면, time[K]를 출력하고,
  경로는 find_path 함수를 통해 찾는다. 리스트 path에 저장된 이전 값들을 거슬러 올라가며 첫 출발 지점에 도달하면 리턴하면 된다.