-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy path13913.py
More file actions
38 lines (33 loc) · 1.11 KB
/
13913.py
File metadata and controls
38 lines (33 loc) · 1.11 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
from collections import deque
n, k = map(int, input().split())
visited = [0] * 100001
prev = [-1] * 100001 # 자신의 이전 노드
queue = deque()
queue.append(n)
visited[n] = 1
while queue:
current = queue.popleft()
if current - 1 >= 0:
if visited[current - 1] == 0:
visited[current - 1] = visited[current] + 1
prev[current - 1] = current # 경로 추적을 위해
queue.append(current - 1)
if current + 1 <= 100000:
if visited[current + 1] == 0:
visited[current + 1] = visited[current] + 1
prev[current + 1] = current # 경로 추적을 위해
queue.append(current + 1)
if current * 2 <= 100000:
if visited[current * 2] == 0:
visited[current * 2] = visited[current] + 1
prev[current * 2] = current # 경로 추적을 위해
queue.append(current * 2)
# 경로 추적 결과 출력
result = [k]
cur = k
while prev[cur] != -1:
cur = prev[cur]
result.append(cur)
print(visited[k] - 1) # 최단 거리 출력
for x in reversed(result): # 경로 출력
print(x, end=" ")