백준 13913 - 숨바꼭질4

12345678910111213141516171819202122232425262728293031from collections import dequeimport sys def bfs(): q = deque() q.append(n) while q: x = q.popleft() if x == k: break for y in x-1, x+1, x*2: if 0 <= y <= 100000 and visit[y] == -1: q.append(y) visit[y] = x n, k = list(map(int, input().split()))visit = [-1] * 100001visit[n] = -2 bfs() ans = []while k != -2: ans.append(k) k = visit[k] ans.reverse()print(len(ans)-1)print(' '.join(map(str, ans)))cs bfs로 평범하게 q에 경로를 같이 담으면 메모리 초과가 발생한다. 이에 visit리스트를 만들어 해당 경로의 이전 위치를 담는다.이후 거꾸로 탐색해가며 경..........

원문링크 : 백준 13913 - 숨바꼭질4