[백준] 1697 숨바꼭질(Python)

1. 생각 정리

• 수빈이의 위치에서 동생의 위치까지 무조건 동생과 가까워지는 루트만 따라가면 오히려 시간이 오래 걸릴 수도 있다.
• 그러므로 각 프로세스마다 (프로세스 단계 * 3)만큼 다양해지는 모든 경우를 고려하여 그중 동생의 위치까지 갔을 때 지금까지 소요된 시간 출력

• 

• 크기가 100001인 일차원 리스트에 각 위치마다 시간이 얼마나 걸렸는지 갱신하며 동생을 찾을 수 있는 가장 빠른 시간을 구하기

 

2.  메모리 초과 코드

#메모리 초과
from collections import deque

N,K = map(int, input().split())

def bfs(n,k):
    q = deque([N])
    result = 0
    count = 1
    while q:
        pos = q.popleft()
        if pos == K:
            print(result)
            break
        q.append(pos+1)
        q.append(pos-1)
        q.append(2*pos)
        if len(q) == 3**count:
            count+=1
            result+=1                   
bfs(N,K)

 

3. 성공 코드

from collections import deque

MAX = 100001
N,K = map(int, input().split())
mapp = [0]*MAX
def bfs():
    q = deque([N])
    while q:
        pos = q.popleft()
        if pos == K:
            return mapp[pos]
        for next_pos in (pos-1, pos+1, pos*2):
            if 0<=next_pos<MAX and not mapp[next_pos]:
                mapp[next_pos] = mapp[pos]+1
                q.append(next_pos)
                
print(bfs())