[자료구조] BFS 알고리즘

자료구조 - 그래프 탐색

그래프 탐색이란?

하나의 시작점 노드에서 연결된 노드들을 모두 찾는 것.

이런 무방향 그래프가 있다고 해보자. B 노드에서 탐색을 시작한다고 할 경우, 결국 모든 데이터를 돌게 된다. 그래프 같은 경우에도 연결된 모든 데이터를 순회하므로 그래프 순회라고도 부른다.

그래프 순회를 통해 알 수 있는 것은, A - BCD 이런식으로 A만 빼고 B ~ D가 연결이 되어 있는 그래프의 경우 A와 B, C, D는 서로 연결되지 않았다는 사실이다.

탐색을 사용하는 또다른 대표적인 예시는 그래프에서 두 노드 사이 최단 경로를 구하는 방법이다. 그래프 순회를 통해 A와 D 사이에 몇 다리가 걸쳐 있는지를 알 수 있게 된다.

그래프 탐색 알고리즘은, 각 노드를 어떤 순서로 탐색하는지에 따라

1. BFS(Breadth First Search)
2. DFS(Depth First Search)

로 나눌 수 있다.

BFS(Breath First Search)

Breadth는 너비를 뜻한다. 깊이 등과 반대되는 표현이다. Breadth(너비를) First(우선적으로) Search(찾는다) 인 것이다.

노드 A에서 탐색을 시작한다고 해 보자.

1. A에 인접한 노드를 찾는다. (B, C)
2. B, C에 인접한 노드를 찾는다. (D, E, F)
   ..

이런식으로 시작점에서 가까운 노드들을 먼저 탐색한다. 계속 실행시키면 전부를 순회하게 된다.

이 경우 수평적인 부분을 먼저 탐색하기 때문에 Breadth가 기준이 되는 것이다.

BFS 알고리즘

이러한 그래프와 빈 큐가 있다고 해보자. BFS는 시작점 노드 A를 받는다. 알고리즘을 진행하면서 이미 방문한 노드와 그렇지 않은 노드를 구분해야 한다.

A 방문 후 큐에 넣는다. 그 후 큐에 들어있는 노드가 없을 때까지 반복문을 돌린다.

1. 큐의 가장 앞 노드 (A)를 꺼낸다.
2. A에 인접한 모든 노드를 돈다. (이미 방문한 노드는 제외한다)
3. 방문하지 않은 노드에 대해, 방문한 노드 표시를 해준 뒤 큐에 넣는다.

4. 이제 C로 간다. C도 방문하지 않았는데, 마찬가지로 방문 노드 표시를 해준 뒤 큐에 넣는다.

이제 A에 인접한 모든 노드를 돌았다. 다시 큐의 가장 앞 노드(B)를 꺼낸다. 이후 B와 인접한 노드를 돈다.

A는 이미 방문한 노드이므로 건너뛰고, D로 간다. D는 아직 방문하지 않았으므로 방문 노드 표시를 한 후 큐에 넣어준다.

이제 C에 인접한 노드를 돈다. A는 방문한 노드이므로 건너뛰고 E, F의 순서대로 큐에 넣어준다.

다 돌고 난 뒤에, 맨 앞 노드를 차례대로 꺼내서 인접한 노드들을 살핀다. 이미 모든 노드를 다 돌았으므로 차례대로 큐에서 제거된다.

큐에 아무 노드도 남아있지 않은 경우 A에서 연결된 노드들을 모두 찾은 것이다. 그리하여 탐색이 끝난다. 결과적으로 면, A, B, C, D, E, F, G, H의 순서로 돌았는데, 이는 그래프가 위에서 아래보다 옆으로 먼저, 너비 우선적으로 탐색된 것이다.

BFS 알고리즘을 일반화해보면:

- 시작 노드를 방문 표시한 후, 큐에 넣는다.
- 큐에 아무 노드가 없을 때까지: (반복)
  - 큐 가장 앞 노드를 꺼낸다.
  - 꺼낸 노드에 인접한 노드들을 모두 보면서:
    - 처음 방문한 노드면:
      - 방문한 노드 표시를 해준다.
      - 큐에 넣어준다.