CS/Algorithm 문제
[BaekJoon] 백준 13913번 숨바꼭질4
심심231
2021. 10. 28. 23:24
[BaekJoon] 백준 13913번 숨바꼭질4
🎈문제
https://www.acmicpc.net/problem/13913
💬설명
- bfs로 풀면서 그냥 큐에 모든 경로를 저장하면 시간초과가 난다.
- before 배열에 해당 위치 직전에 방문한 곳을 저장해줘서 마지막에 한번에 출력했다.
👩💻코드
# BaekJoon13913.py
from collections import deque
N, K = map(int, input().split())
visited = [False for _ in range(100001)]
before = [-1 for _ in range(100001)] # 이동 경로 저장
queue = deque([[N, 0]]) # 수빈이 위치
def print_path(time):
global before, K
arr = []
tmp = K
for _ in range(time):
arr.append(tmp)
tmp = before[tmp]
print(' '.join(map(str, arr[::-1])))
while queue:
value = queue.popleft()
# 수빈이가 동생과 만나는 경우
if value[0] == K:
print(value[1])
print_path(value[1] + 1)
break
new = [value[0] - 1, value[0] + 1, value[0] * 2]
for i in range(3):
if new[i] < 0 or new[i] > 100000 or visited[new[i]]:
continue
visited[new[i]] = True
queue.append([new[i], value[1] + 1])
before[new[i]] = value[0]
728x90
반응형