[BOJ] #1697 숨바꼭질 (Python, BFS, 메모리 초과 문제 해결)

💡 문제

1697번: 숨바꼭질

 

💡 풀이

처음에는 단순히 간단한 BFS 문제라고 생각하여 아래와 같이 코드를 작성했더니 메모리 초과가 났습니다. 그 이유는 n과 k가 100,000까지 될 수 있는데, while문을 돌면서 queue가 계속 3배가 되기 때문입니다.

# !/usr/bin/env python
# -*- coding: utf-8 -*-
# boj 1697 숨바꼭질

import sys
from collections import deque

input = sys.stdin.readline

n, k = map(int, input().split())
answer = 0

queue = deque([])
queue.append([n, 0])
while queue:
    i, cnt = queue.popleft()
    if i == k:
        answer = cnt
        break
    queue.append([i - 1, cnt + 1])
    queue.append([i + 1, cnt + 1])
    queue.append([i * 2, cnt + 1])

print(answer)

이렇게 단순히 큐에 -1한 값, +1한 값, x2한 값을 무조건 넣어주게 되면, 중복해서 queue에 넣어지게 되는 값이 매우 많습니다. 즉, 한번 검사했던 것들을 계속 검사하게 됩니다. 따라서 queue에 넣기 전에 조건문을 통해 방문했었는지 검사하는 것이 필요합니다. 

처음에 방문 여부를 검사하는 리스트를 만드는 것을 생각했었는데, n과 k의 범위가 10만까지여서 너무 크다고 생각해서 리스트를 따로 만들지 않았습니다. 그러나 1byte짜리 boolean 변수가 100,000개이면 100,000 byte = 100 KB 정도밖에 되지 않으므로 문제에서 준 124MB 메모리에서는 충분히 사용 가능합니다.

따사러 queue에 넣으려는 값이 0과 100,000 사이의 값인지 확인하고, 해당 값을 방문한 적이 없다면 queue에 넣어주도록 조건문을 추가하였습니다.

 

💡 정답 코드

# !/usr/bin/env python
# -*- coding: utf-8 -*-
# boj 1697 숨바꼭질

import sys
from collections import deque

input = sys.stdin.readline

n, k = map(int, input().split())
answer = 0
visited = [False] * 1000001

queue = deque([])
queue.append([n, 0])
while queue:
    i, cnt = queue.popleft()
    if i == k:
        answer = cnt
        break
    if 0 <= i - 1 <= 1000000 and not visited[i - 1]:
        visited[i - 1] = True
        queue.append([i - 1, cnt + 1])
    if 0 <= i + 1 <= 1000000 and not visited[i + 1]:
        visited[i + 1] = True
        queue.append([i + 1, cnt + 1])
    if 0 <= i * 2 <= 100000 and not visited[i * 2]:
        visited[i * 2] = True
        queue.append([i * 2, cnt + 1])

print(answer)