백준 1697번 BFS

서론

1697번: 숨바꼭질

생각해보지 못한 BFS 문제였습니다. BFS 카테고리에 없었으면 왠지 DP를 활용해서 문제를 풀어보려고 했을 것 같습니다. 시간이 되면 DP로도 풀어보겠습니다. BFS로 풀 수 있는 새로운 유형을 익혔고 풀면서 일반적인 BFS 문제에서 이미 탐색했던 곳을 중복하여 탐색하는 것을 피하고자 사용하는 방법에서 고찰이 있어서 적습니다.

저는 이미 짜여 있는 코드 구조를 많이 참고하기도 했고 이제는 익숙해져서 중복을 피하고자 탐색했던 노드를 visited라는 리스트 안에 넣어놓고 판단합니다. if node not in visited 이런 식의 코드를 사용하는데 이번 문제에서도 이렇게 코드를 사용하였더니 시간초과가 나와서 다른 코드를 참조하여 visited = [1]*100001같은 방법을 사용하였습니다. 사실 graph나 map 전체를 bool 타입으로 만들어놓고 map과 비교하며 탐색하는 방법은 기존에도 썼었는데 이번 문제는 뭔가 다르게 생긴 것 같아 적용을 못 했습니다.

어쨌거나 위에서 if node not in visited를 통해 node를 탐색한 적이 있는지 확인하면 시간복잡도가 이 되고 visited = [1]*100001를 통해 인덱스로 접근하여 확인하면 시간복잡도가 O(1)의 됩니다. 문제에 조건에 맞게 십만 개의 데이터 공간을 추가로 사용할 수 있다면 모든 경우를 bool 타입으로 만들어 놓고 탐색하는 것이 유리합니다.

제한 조건

BFS, DFS 문제들은 제한을 심하게 두진 않기 크게 신경 쓰지 않아도 된다고 생각했는데 위처럼 활용 가능한 메모리가 있는지 보는 정도는 문제 푸는데 도움이 될 것 같습니다. 그래도 최적화를 위해서 탐색해야 하는 graph나 map은 한 번만 훑는 것이 좋고 또 함수를 사용한다면 함수 내에 인자로 전달해서 괜히 복사하여 시간과 메모리를 잡아먹지 말고 그냥 전역변수로 사용하는 것이 좋습니다.

• 시간제한 - 2초

시간제한은 2초입니다. 일반적인 컴퓨터로 1초에 1억 번 연산한다는 기준을 가지고 풉니다. map의 최대 크기가 100,000이고 결국 수빈이가 동생한테 가는 길을 중복 없이 한 번씩 탐색하기 때문에 100,000번 탐색한다고 볼 수 있고 그 탐색 루프 안에서 que를 popleft() 하니 O(1), visited를 인덱스로 참조하니 O(1), 결과적으로 총 시간복잡도는 100,000인 O(n)로 볼 수 있습니다.

처음에 틀렸을 때 탐색 루프 안에서 시간복잡도 O(n)을 가지는 if node not in visited를 사용했기 때문에 전체시간복잡도가 O(n^2) 되어서 시간초과가 났습니다.

• 메모리 제한 - 128MB

메모리 제한은 128MB입니다. 경로상의 데이터 개수는 십만 개지만 여기서는 map 자체를 선언하지도 않고, que는 넣었다 뺐다 하니 크게 잡아먹지 않고, visited 정도가 잡아먹는데 visited를 bool 타입으로 10만 개 선언해도 충분한 크기입니다. 역시 메모리를 괜히 복사하지 않기 위해 전역변수로 사용하는 것이 좋겠습니다.

BFS

푸는 방법 자체가 어렵진 않았기 때문에 푸는 방법을 설명하진 않겠습니다. 그래도 고찰 사항이 있었으니 시간 초과인 코드와 정답 코드 모두 올립니다.

## 시간 초과 코드입니다.
from collections import deque as dq
import sys
input = sys.stdin.readline

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

def bfs(n,k):
    que = dq()
    visited = []
    que.append([n,0])

    while que:
        node = que.popleft()
        if node[0] ==k:
            return node[1]
        else:
            if node[0] not in visited:
                visited.append(node[0])
                if node[0]-1 not in visited and (node[0]-1>=0 and node[0]-1<=100000):
                    que.append([node[0]-1,node[1]+1])
                if node[0]+1 not in visited and (node[0]+1>=0 and node[0]+1<=100000):
                    que.append([node[0]+1,node[1]+1])
                if node[0]*2 not in visited and (node[0]*2>=0 and node[0]*2<=100000):
                    que.append([node[0]*2,node[1]+1])

print(bfs(n,k))

# 정답 코드입니다.
from collections import deque as dq
import sys
input = sys.stdin.readline

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

def bfs(n,k):
    que = dq()
    visited = [1]*100001
    que.append([n,0])

    while que:
        node = que.popleft()
        if node[0] ==k:
            return node[1]
        else:
            if visited[node[0]]:
                visited[node[0]] = 0
                if (node[0]-1>=0 and node[0]-1<=100000) and visited[node[0]-1]:
                    que.append([node[0]-1,node[1]+1])
                if (node[0]+1>=0 and node[0]+1<=100000) and visited[node[0]+1]:
                    que.append([node[0]+1,node[1]+1])
                if (node[0]*2>=0 and node[0]*2<=100000) and visited[node[0]*2]:
                    que.append([node[0]*2,node[1]+1])

print(bfs(n,k))

생각

탐색 루프 안에서 사용한 popleft() 코드가 파이썬에서 제공하는 deque모듈을 사용하면 O(1)이지만 파이썬의 리스트를 사용해서 구현하면 O(n)이 됩니다. 이러면 마찬가지로 전체 탐색이 O(n^2)이 돼서 시간초과로 실패할 텐데, 모듈을 사용하지 않거나 다른 언어로 구현하게 되면 어떤 식으로 구현해야 할지 생각해볼 필요가 있습니다.