[자료구조] 14-1. 넓이 우선 탐색 알고리즘

BFS를 얘기하기 전에 먼저 전체적인 체계를 다시 한 번 살펴보자.

그래프에 대한 연산 중 가장 많이 사용되는 것은 DFS와 BFS이다. 지금까지는 DFS에 대해 공부했고, 그와 관련된 연결 성분, 신장 트리, 이중 연결 성분 등에 대해 공부했다.

이번에는 BFS를 배우고 여기에 영향을 받은 최단 거리 구하는 알고리즘에 대해 알아보도록 하자.

그래프에서의 탐색 문제는 서치 또는 트래버셜이라고 부르며, 한 버텍스 v부터 시작해 모든 버텍스를 방문하는 방법을 알아내는 것이다.

탐색을 하는 과정에서 중요한 요소는,

1. 한 번 탐색은 노드는 기록한다. 그래야 두 번 다시 방문하지 않을 것이기 때문이다. visit 배열이 추가적으로 필요하다.

2. 버텍스를 방문하는 순서를 기억한다. 이를 위한 자료구조로 스택이나 큐가 사용된다.

저번 시간에는 스택을 이용한 DFS를 공부했다. 이때 스택은 DFS의 재귀 호출 형태로 구현되기 때문에 시스템 스택을 사용하게 된다. 다시 말해, 스택을 특별히 정의하지 않아도 사용할 수 있었다.

하지만 큐를 이용하는 BFS는 명시적으로 큐를 정의해줘야 한다.

BFS는 방문할 버텍스의 리스트를 큐를 이용해 관리하며, 명시적으로 큐를 선언해줘야 한다고 말했다. 그래서 기본적으로 while(!queue) 즉, queue가 엠티가 아닌 동한 수행되는 루프가 포함된다.

1. 큐를 시작할 때는 맨 처음 원소로 임의의 버텍스 v0 하나를 추가한다.

2. while문 안에 들어가서 큐를 pop하고, 다음에 방문할 버텍스를 선택한다.

3. v에 연결된 버텍스 중에서 아직 방문하지 않은 것이 있다면 방문한 것으로 표시하고 큐에 추가한다. 즉, push(w)를 수행한다.

4. 큐가 empty가 아닌 동안 계속 반복한다.

1. 큐를 사용하므로 일단 front와 rear를 -1 또는 null로 초기화한다.

2. 해당 버텍스를 방문했음을 표시해준다.

3. 큐에 버텍스를 넣는다.

4. 큐가 empty가 아닌 동안 while을 수행한다.

5. while 안에서는 큐에서 원소 하나를 꺼내 방문하려고 하는 다음 버텍스를 선택한다.

6. 이 버텍스에 연결된 모든 버텍스에 대해, 방문하지 않았다면 방문한 것으로 표시하고 큐에 삽입한다.

BFS의 시간 복잡도를 알아보자. 코드를 보면 두 개의 반목문이 중첩된다. 밖에 있는 while은 모든 버텍스에 대해 수행하므로 O(n)이다. 따라서 안에 있는 for문은 O(n)만큼 수행된다.

하지만 for 루프의 연산 시간은 각 버텍스에 연결된 엣지의 수에 비례할 것이다. 그래프를 인접 행렬로 구현했다면 O(n)이 될 것이고, 인접 리스트를 이용해서 구했다면 연결된 버텍스의 수만큼 걸릴 것이다. 희소 그래프라면 O(1)이고 밀집 그래프나 완전 그래프라면 O(n)의 시간이 걸리기 때문이다.

DFS와 마찬가지로, for 루프가 수행되는 것을 버텍스 보다 엣지의 관점에서 살펴보자.

v와 w가 엣지로 연결되어 있다면,

1. v에서 아직 방문하지 않은 w를 큐에 집어 넣을 때

2. w가 큐에서 나와서 연결된 v를 이미 방문했는지 확인할 때

이렇게 이 엣지를  두 번 방문하게 될 것이다. 이렇게 모든 엣지를 두 번씩 방문한다고 생각하면, BFS는 엣지의 수가 m일 때 O(m)이 걸린다. 만약 엣지가 없는 disconnected 그래프라면 O(n)이 된다. 이때 n은 v이다.

따라서 BFS의 시간 복잡도는 O(n+m)이다.

BFS의 과정을 살펴보자. 버텍스를 방문했는지 알아보는 visit 배열과, 방문한 순서를 저장하기 위한 queue가 필요하다. queue에 필요한 연산은 push, pop, empty Q 3가지다.

이 그래프에서 bfs(0)을 하면, dfs와 마찬가지로 오름차순으로 버텍스를 방문한다. 0번의 visit을 1로 바꾸고, 큐에 넣는다.

그러면 while 루프에 진입해서 pop을 한다. 큐에 있는 0번이 pop된다. 이때 0번 버텍스에 연결된 w는 1과 2가 있다.

1과 2는 아직 방문하지 않았으므로 visit을 1로 바꿔주고, 큐에 넣어준다.

이렇게 마무리된다.

그럼 다시 while문을 반복하게 되는데, 아직 큐가 empty가 아니가 때문에, 큐에서 pop한 1이 나온다.

1에 연결된 버텍스는 0, 3, 4가 있는데 0은 이미 방문했으므로 3과 4를 비지트로 표시하고 큐에 집어넣는다.

이렇게 마무리 하고 또 while 루프의 처음으로 돌아간다.

while 루프에 들어와서 pop을 하면 큐의 맨 앞에 있는 2가 나온다. 

2에 연결된 0, 5, 6 중 아직 방문하지 않은 5, 6을 visit 표시 해주고 큐에 넣는다.

다시 while문을 돌며 pop을 시작하면 3이 나온다. 1과 7 중 방문하지 않은 7로 간다.

7의 visit을 1로 바꾼다.

push 한다. 

다시 돌아와 큐 맨 앞의 4를 pop한다.

이미 다 방문했으므로 그 다음에 있는 5를 pop한다.

역시 다 방문했으므로 6을 pop 하고

6도 주변 버텍스를 다 방문했으므로 7을 pop한다. 7도 방문할 버텍스가 없다. while은 queue가 empty일 때 반복되는데 지금 empty가 되었으므로 while도 끝난다.

bfs를 수행하면 0번부터 시작해 0번에 연결된 모든 버텍스들을 다 차례대로 방문했다. 그런데 dfs와 비교하면 약간의 차이가 있다. 버텍스를 방문한 순서를 보면, 방문을 시작한 노드로부터 떨어진 엣지의 수만큼 그 다음에 방문하게 된다.

따라서 bfs는 거리를 반영하는 특징이 있다. dfs는 두 번 방문하기 때문에 거리를 측정할 수 없다.