알고리즘 2) BFS

BFS(Breadth-First Search) 알고리즘

• BFS는 깊이 우선 탐색이라고도 부르며 그래프에서 가까운 노드부터 탐색하는 알고리즘이다.
• 최대한 멀리 있는 노드를 우선으로 탐색하는 DFS와는 반대다.
• 최단 경로를 찾는 문제에서 주로 사용된다.
• BFS는 선입선출 방식인 큐 자료구조를 이용한다.
• 인접한 노드를 반복적으로 큐에 넣도록 알고리즘을 작성하면 자연스럽게 먼저 들어온 것이 먼저 나나게 되어, 가까운 노드부터 탐색을 진행하게 된다. 구체적인 동작은 아래와 같다.

1. 탐색 시작 노드를 큐에 삽입하고 방문 처리를 한다.
2. 큐에서 노드를 꺼내 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리를 한다.
3. 더 이상 2번의 과정을 수행할 수 없을 때까지 반복한다.

step 1. 아래와 같은 그래프가 있다고 하자

(현재 큐에서 꺼낸 노드는 회색으로, 방문처리한 노드는 검정색으로, 방문하지 않은 노드는 흰색으로 표시한다.)

step 2. 1을 큐에 넣고 방문 처리한다.

step 3. 1을 큐에서 뺀다. 1과 인접한 2, 3을 큐에 넣고 방문 처리한다.

step 4. 2를 큐에서 뺀다. 2와 인접한 4, 5를 큐에 넣고 방문 처리한다.

step 5. 3을 큐에서 뺀다. 3과 인접한 6, 7을 큐에 넣고 방문 처리한다.

step 6. 4를 큐에서 뺀다. 4와 인접한 8을 큐에 넣고 방문 처리한다.

step 7. 5를 큐에서 뺀다. 5와 인접한 9를 큐에 넣고 방문 처리한다.

step 8. 큐에 남은 노드의 인접 노드 중에서 방문하지 않은 노드가 없다. 따라서 남은 노드를 차례대로 꺼낸다.

step 9. 완성

from collections import deque

def bfs(v):
    visited[v] = True
    queue = deque([v])

    while queue:
        x = queue.popleft()
        print(x, end=' ')

        for i in graph[x]:
            if not visited[i]:
                visited[i] = True
                queue.append(i)


# 각 노드가 연결된 정보를 표현
graph = [
    [],  # 0번 노드가 없으므로 index 0은 비워둠
    [2, 3],  # 1번 노드와 연결된 노드
    [1, 4, 5],
    [1, 6, 7],
    [2, 8],
    [2, 9],
    [3],
    [3],
    [4],
    [5]
]

# 각 노드가 방문된 정보를 표현
visited = [False]*10

bfs(1)

출력 : 1 2 3 4 5 6 7 8 9

Outro

BFS 또한 탐색 알고리즘으로 그래프 그림을 이용해 1차원 배열이나 2차원 배열을 그래프 형태로 생각하면 BFS를 이용해 문제를 수월하게 풀 수 있다.

코딩 테스트에서 보통 DFS로 풀 수 있으면 BFS로도 풀 수 있고, 이 반대도 마찬가지이다(보통 DFS보다는 BFS 구현이 조금 더 빠르게 동작한다).

하지만 문제에 따라 더 효율적인 풀이가 될 수 있는 방법이 있으므로 여러 문제를 풀어보며 더 나은 해결 방법을 잘 생각해보자.