백준_python 13549번 숨바꼭질 (메모리 초과, BFS, 최단거리)

<문제 링크>

https://www.acmicpc.net/problem/13549

 

 

<정답 코드>

 sol1 ) 나의 오답 - 메모리 초과

from collections import deque
n, k = map(int, input().split())
graph = deque([(n, 0)])
 
while True:
    now, time = graph.popleft()
    
    if now == k:
        print(time)
        break
 
    graph.append((now * 2, time))
    graph.append((now + 1, time + 1))
    graph.append((now - 1, time + 1))

 

예제는 맞췄지만, 채점 시 메모리 초과 발생

 

틀린 이유

1. 중복 방문 체크 없음 : 동일 위치 여러번 방문, 큐에 추가

2. 무한 이동 : 이동 후 위치가 목표값인 k를 넘는 경우에도 체크하지 않고 무한 추가

3. 무한 루프 가능성 : 이동 후 위치가 음수인 경우도 체크하지 않고 큐에 추가

4. 비효율적인 큐 처리 : 순간이동의 경우 시간 증가하지 않음에도 큐 맨뒤에 추가

 

 

 

 sol2 ) BFS로 탐색 - 정답

import sys
from collections import deque
input = sys.stdin.readline
 
def bfs(now, target):
    q = deque([now])
    time[now] = 0   # 방문 처리
 
    while q:
        x = q.popleft()
        # 현재 위치가 target(동생 위치)와 일치하면 시간 리턴
        if x == target:
            return time[x]
        
        for nx in (x-1,x+1,x*2):
            if 0<= nx < limit and time[nx] == -1:
                if nx == 2*x:
                    time[nx] = time[x]
                    # 시간 증가하지 않았으므로 q 맨 앞 추가
                    q.appendleft(nx)    
                else:
                    # 시간 1 증가, q 맨 뒤에 추가
                    time[nx] = time[x] +1
                    q.append(nx)
 
 
# 현재 위치 p, 목표 위치 t 입력 받기
p, t = map(int, input().split())
limit = 100001
time = [-1] * limit     # 방문 체크 및 시간 저장
 
print(bfs(p, t))

1번 오답 코드의 문제점들을 개선해

- visited 배열로 방문 체크

- 이동 후 위치 범위 체크

- 시간 증가하지 않는 순간이동은 큐 맨 앞, 나머지 시간 증가하는 이동은 큐 맨 뒤에 추가

하여 효율적 메모리 사용 가능하도록 개선

 

 

 

 

 

문제에서 주어진 범위 조건들이 메모리 초과, 시간 초과 문제를 해결하기 위한 단서

방문 여부 확인 중요