이 포스팅은 Algorithm Problem Solving 시리즈 113 편 중 39 번째 글 입니다.
목차
골드4 : BFS 문제이다.
풀이
아니 풀이방법을 아는데 왜 코드가 안돌아가는지 모르겠다. 계속해서 메모리 초과가 뜨는데 어떤 부분이 문제인지 아직도 못찾았다..
Code
from collections import deque
import sys
# sys.setrecursionlimit(int(1e6))
# input = sys.stdin.readline
N, K = map(int, input().split())
visited = [-1] * 100001
path = []
def BFS():
q = deque()
q.append((N, 0))
visited[N] = N
while q:
pos, time = q.popleft()
if pos == K:
a = pos
while a != N:
path.append(a)
a = visited[a]
path.append(a)
return time
if pos + 1 < 100001 and visited[pos + 1] == -1:
q.append((pos + 1, time + 1))
visited[pos + 1] = pos
if pos - 1 >= 0 and visited[pos - 1] == -1:
q.append((pos - 1, time + 1))
visited[pos - 1] = pos
if pos * 2 < 100001 and visited[pos * 2] == -1:
q.append((pos * 2, time + 1))
visited[pos * 2] = pos
print(BFS())
print(path[::-1])
from collections import deque
import sys
n, k = map(int, input().split())
visited = [-1] * 100001 # 방문여부까지 확인하기 위해 -1로 초기화
path = [] # 지금까지 방문 경로 저장
def bfs(start, target):
queue = deque()
queue.append((n, 0))
visited[start] = start
while queue:
cur, cur_time = queue.popleft()
if cur == target: # 동생을 찾음
idx = cur
while idx != start:
path.append(idx)
idx = visited[idx] # 이 부분이 중요!
path.append(start) # 첫 시작점까지 넣는다
return cur_time
if cur + 1 < 100001 and visited[cur + 1] == -1:
queue.append((cur + 1, cur_time + 1))
visited[cur + 1] = cur
if cur - 1 >= 0 and visited[cur - 1] == -1:
queue.append((cur - 1, cur_time + 1))
visited[cur - 1] = cur
if cur * 2 < 100001 and visited[cur * 2] == -1:
queue.append((cur * 2, cur_time + 1))
visited[cur * 2] = cur
print(bfs(n, k))
print(*path[::-1]) # 뒤에서 부터 출력
# 위의 코드가 왜안되는지 돚2ㅓ히 알 수가 없다.