[백준] 13913. 숨바꼭질 4(Python, 파이썬)

백준 온라인의 문제 풀이입니다.

📖 [백준] 13913. 숨바꼭질 4

시간 제한	메모리 제한	난이도
2초	512 MB	골드 4

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

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

✔️ 입력

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

✔️ 출력

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

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

✔️ 입력 출력 예시

입력	출력
5 17	4 5 10 9 18 17
5 17	4 5 4 8 16 17

🗒️ 내 풀이

[1697. 숨바꼭질]에서 경로를 출력하는 문제이다. 따라서 BFS를 통해 해결할 수 있다.

이전 노드를 기록하는 리스트를 만들고, q에 append 할 때 마다 해당 위치의 이전 노드를 기록하도록 했다.

처음에는 path를 기록하는 리스트를 q에 넣어주고 q에 append 할 때 해당 path에 다음 경로를 추가하는 방법으로 했었는데, 리스트를 계속 생성해줘야 하다보니 시간초과가 발생했다.

🌟 통과 코드

import sys
from collections import deque
input = sys.stdin.readline
n, k = map(int, input().split())
q = deque([(n)])
dist = [-1] * 100001 
route = [-1] * 100001 # 이전 노드를 기록
dist[n] = 0
while q:
    x = q.popleft()
    if x == k:
        print(dist[k])
        result = [k]
        for i in range(dist[k]):
            result.append(route[result[-1]])
        print(*result[::-1])
        break
    for i in [x * 2, x + 1, x - 1]:
        if 0 <= i <= 100000 and dist[i] == -1 :
            dist[i] = dist[x] + 1
            route[i] = x
            q.append(i)

😂 시간초과 코드

import sys
from collections import deque
input = sys.stdin.readline
n, k = map(int, input().split())
q = deque([(n, 0, [n])])
visited = [False] * 100001 
while q:
    x, time, path = q.popleft()
    visited[x] = True
    if x == k:
        result = time
        path = path
        break
    for i in [x * 2, x + 1, x - 1]:
        if i == k:
            result = time + 1
            path = path + [i]
            q.clear()
            break
        if 0 <= i <= 100000 and not visited[i]:
            temp = path + [i]   # 시간초과되는 부분 O(N)의 시간 복잡도
            q.append((i, time + 1, temp))

print(result)
for p in path:
    print(p, end=' ')

💡 TIL

시간 복잡도 항상 생각하기!!