[Python] 백준, 1697(BFS)

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

1697번: 숨바꼭질

이쪽 문제들은 왜 이렇게 변태 같을까. 진짜 고생했다. 한발 다가가면 두발 멀어지는 놈들이다. 어제 유튜브 알고리즘에 켠 김에 백준 루비 티어 찍는다는 컨셉의 영상도 있더라... 나도 변태 같은 개발자가 되어야겠다.

 

BFS로 접근해야하는 이유는 같은 레벨일 때(걸린 시간이 같을 때)의 케이스들을 따져야 하기 때문이다.

 

 

 

# PYTHON CODE (1)

from collections import deque

n, m = map(int, input().split())
visit = [0] * 100001

def bfs(x):
    queue = deque()
    queue.append(n)

    while queue:
        a = queue.popleft()

        if a == m:
            print(visit[a])
            break

        for j in (a - 1, a + 1, a * 2):
            if 0 <= j <= 100000 and visit[j] == 0:
                visit[j] = visit[a] + 1
                queue.append(j)

bfs(n)

우리가 주목해야하는 포인트는 2가지다.

 

 1) for문에서의 순서가 (a - 1, a + 1, a * 2)인 이유는 n = 0, m = 1인 테스트 케이스를 피하기 위함이다.

 2) if문의 visit은 중복을 피하기 위함이며 실제로 a에 값을 넣고 실제 visit이 변화하는 양상을 보면 알고리즘을 이해하기 쉬워진다.

 

 

근데 처음에 내가 구상했던 풀이는 토마토 풀이에서 사용했던 큐를 갱신하며 cnt를 1씩 증가해주는 풀이였기 때문에 이런 방식으로 코드를 재구상했으나, 백준 풀이 처음으로 메모리 초과를 마주쳤다.

 

# PYTHON CODE (2) - 메모리 초과

m, n = map(int, input().split())

queue = []
new_queue = []
queue.append(m)
flag = False
cnt = 1

while queue:
    for i in queue:
        next_x = [i * 2, i + 1, i - 1]
        if n in next_x:
            flag = True
            break
        new_queue += next_x
    if flag:
        break
    new_queue = list(set(new_queue))
    queue = new_queue
    new_queue = []
    cnt += 1

if n == m:
    print(0)
else:
    print(cnt)

테스트 케이스의 경우나 직관적인 이해에 있어서는 문제가 없어보이지만, 메모리 초과가 극복이 안됐다. 물론 지금 다시 코드를 분석해보면 그리 효율적인 코드는 아니라고 판단되긴 한다.

 

1) 이미 방문했던 곳을 재방문하는 경우가 생긴다.

2) n in next_x 부분의 효율성이 떨어진다. next_x 배열의 길이가 길어질수록 비효율적이다.

 

 

이러한 문제점과 맞은 사람의 풀이 중 접근 방법이 나와 유사한 풀이를 참고하여 코드를 다시 짜봤다.

 

# PYTHON CODE (3)

m, n = map(int, input().split())

queue = [m]
flag = False
cnt = 0
visit = [False] * 100001

while queue:
    new_queue = []
    for i in queue:
        if i == n:
            print(cnt)
            flag = True
            break

        for j in (i - 1, i + 1, i * 2):
            if 0 <= j <= 100000 and not visit[j]:
                visit[j] = True
                new_queue.append(j)
    if flag:
        break

    queue = new_queue
    cnt += 1

우선 n == m인 경우를 따로 확인하지 않아도 되며, next_x라는 배열을 따로 만들 필요 없이 for문을 추가로 작성하여 조건에 맞는 값만 new_queue배열에 append한다. 

 

queue값을 new_queue로 갱신해주면서 주기를 유지한다.

 

 

 

원했던 방향으로 문제를 풀어내긴 했지만, (2)의 코드가 왜 메모리 초과를 야기하는지에 대해서는 아직 잘 모르겠다. 예전 포스트에서 시간 복잡도에 대한 언급을 한 적이 있었는데 그와 비슷한 느낌이지 않을까 싶다.