BFS문제, 접근 전략

그래프 탐색 BFS 문제를 처음 접했을 때 어려울 수 있는 점은, BFS 문제에 좌표에 대한 내용이 많이 나오는데 이를 그래프 개념과 연결시키는 부분입니다. 카카오 코딩 테스트 문제(KAKAO BLIND RECRUITMENT 2019~2021)를 직접 풀어보며 이에 대해 정리했던 내용을 공유합니다. 

 

기본 구조

from collections import deque

def bfs(start):
    global n
    dist = [math.inf] * n
    q = deque([])
    q.append(start)
    dist[start] = 0
    while q:
    	node = q.popleft()
        for i in graph[node]:
            # nextCost 계산 
            if nextCost < dist[i]:
            	q.append(i)
                dist[i] = nextCost

BFS 문제에서는 시작 노드와 dist를 필요로 합니다. 이때 dist는 시작 노드로부터 다른 노드까지(1:n)의 최단거리를 저장합니다.따라서 탐색하기전 초기 설정은 두 가지입니다.

1) 큐에 시작 노드를 넣는다.
       q.append(start)
2) 시작 노드까지의 최단거리를 0 설정한다.
       dist [start] =0

그리고 while문을 반복하며 dist의 값을 채웁니다. while문을 일종의 black box로 생각했을 때 입력은 시작 노드, 출력은 시작 노드로부터 최단거리가 채워진 dist입니다. 위의 구조를 단순 암기하고 black box로 생각하면 기본적인 문제는 풀 수 있지만 응용은 할 수 없습니다(처음에는 이렇게 시작해도 좋습니다). 그래서 탐색과정에 대한 이해가 필요합니다.

 

탐색 과정

while문의 탐색과정을 이해하려면 큐의 FIFO에 대한 이해가 선행되어야 합니다. (이에 대한 설명은 흐름을 방해해 생략하였습니다.)

while q:
    node = q.popleft()
    for i in graph[node]:
        # nextCost 계산 
        if nextCost < dist[i]:
            q.append(i)  #i는 nextNode를 의미
            dist[i] = nextCost

1)   큐에서 노드를 꺼낸다.
2)   꺼낸 노드와 연결된 노드들은 다음 탐색할 후보 노드이다. (for문)
3)   후보 중 실제로 탐색할 노드 결정한다. (if문)
4)   실제로 탐색할 노드를 큐에 넣는다.

while문 안에는 같은 형식의 코드가 반복되고 있으며, 이는 탐색하는 과정을 일반화했다고 볼 수 있습니다. 즉, 큐에서 노드를 꺼낸다는 것은 어떤 경로(경우의 수)의 중간지점 노드에서의 상황으로 볼 수 있습니다.

 

문제에 따라 달라지는 부분 (중요)

1) dist vs visited

처음에 설명했듯이 문제에서 최단거리를 구해야 하는 경우 dist를 사용하며(이때 dist는 visited의 역할도 한다.), 탐색만 해도 문제가 풀리는 경우 visited를 사용합니다.

2) dist의 형태

(중요) 노드와 1:1 대응되도록 만들어야 합니다. dist는 if문에서 실제로 탐색할 노드를 결정하는 조건으로 사용되고, 노드까지의 최단거리를 저장한다는 점에서 이를 알 수 있습니다.

3) 큐에 노드를 넣어주는 형태

문제마다 cost를 같이 넣어주는 경우, state를 같이 넣어주는 경우, level을 같이 넣어주는 경우가 있습니다. 기본적인 전략은 경로마다 추적해야 하는 정보를 넣어주는 것입니다. BFS는 모든 경로(경우의 수)를 한 단계씩 처리는데, 노드를 꺼냈을 때 어떤 단계인지 혹은 상황인지를 알아야 하기 때문입니다.

4) 연결된 노드(다음 탐색할 후보 노드) 확인하는 방법 (for문)

좌표계를 포함한 문제에 BFS를 적용할 때, 가장 특징이 되는 부분입니다. 예를 들어, 문제에서 상하좌우로 움직일 수 있다는 말은 노드 간 연결이 상하좌우로 되어 있다는 의미입니다. 즉, 다음 노드 후보는 상하좌우에 위치한 좌표가 됩니다.

for i in range(4):
    nx = x + dx[i]
    ny = y + dy[i]

5) nextCost를 계산하는 방법

큐에서 꺼낸 현재 노드에서, 후보가 되는 다음 노드까지 갔을 때 경로의 비용을 계산합니다. 기본적으로 다음과 같습니다.

nextCost = nowCost + 동일한 weight

nowCost는 3)에서 cost를 추적해야 하는 경우, 큐에서 꺼낸 비용입니다. 만약 cost를 추적하지 않아도 되는 간단한 경우라면 대신 dist [node]를 사용합니다. (참고로 weight가 동일하지 않다면 다익스트라 알고리즘을 사용해야 합니다.)

6) 실제 탐색할 노드를 결정하는 조건 (if문)

if nextCost < dist[i]:

if문의 조건에 등호가 들어가야 하는 경우가 있습니다. 바로 3)에서 state를 같이 넣어준 경우입니다. 먼저 state를 정의하면, 현재 큐에서 꺼낸 노드가 같더라도 지나온 경로에 따라 nextCost가 달라지는 상황을 고려하기 위한 변수입니다.
즉 nextCost가 dist [i]와 같은 경우에도 탐색을 해야 하는 상황이라는 의미입니다. 일반적으로 nextCost = dist [i]인 경우는 이미 다음 노드(i)까지의 최단거리가 구해진 것이므로 탐색할 필요가 없습니다.

---

이러한 개념들을 실제 카카오 기출문제에 적용한 코드를 이후에 공유하도록 하겠습니다.