너비우선탐색 BFS (백준-바이러스)

주소 : https://www.acmicpc.net/problem/2606

[ 너비우선탐색(BFS) VS 깊이우선탐색(DFS) ]

이 문제는 너비우선탐색(이하 BFS) 또는 깊이우선탐색(이하 DFS)로 문제를 해결할 수 있다. 두 가지 탐색방법은 그래프를 탐색할 때 사용하는 알고리즘 기법이다. 

여기서 그래프는 간선과 노드로 이루어진 자료구조를 말한다. 이 말은 위 문제의 그림1에 대입해 볼 수 있다. 그림 1은 그래프 자료구조 형태이다. 숫자 1, 2, 3..을 노드라고 부른다. 그리고 각 노드를 연결하는 선을 간선이라고 한다.

그럼 그래프를 탐색하는 두 가지방법(BFS, DFS)를 설명하겠다. 첫번째 BFS는 시작 노드에서 사방으로 퍼지는 형태로 탐색하는 알고리즘이다. BFS를 그림1에 적용하면 아래와 같이 탐색을 하게 된다.

[ BFS 탐색 순서 ]

1단계

2, 3단계

4, 5단계

BFS로 위의 그래프를 탐색하면 5단계에 걸쳐 탐색을 완료하게 된다. 1 -> 2 -> 5 -> 3 -> 6 순으로 노드를 탐색을 한다.

노드 4, 7(그림 오류 색이 안칠해진 노드 5는 노드7를 의미함)은 다른 노드와 간선으로 연결되어 있지 않기 때문에 탐색할 수 없다.

[ DFS 탐색 순서 ]

단계1

단계2

단계3

단계 4

단계 5

DFS는 위 그래프의 노드를 1 -> 2 -> 3 -> 5 -> 6순으로 탐색한다. 그래서 DFS의 탐색 순서는 한 방향으로 최대한 깊이 탐색한 후에 다른 방향으로 간다.

[ 큐(Queue) 자료구조 이해하기 ]

BFS를 큐(Queue) 자료구조를 이용해서 구현하는 방법을 살펴보겠다. BFS를 구현하기 위해서 '큐'라는 자료구조가 필요하기 때문에 큐를 먼저 살펴보겠다. 큐는 먼저 들어온 데이터를 먼저 빼내는 FIFO(First In First Out) 자료구조이다. 작동하는 순서는 아래 그림과 같다.

1) 큐의 동작순서

데이터 삽입 과정

              

             

                

데이터 제거 과정

      

2) C++ STL로 큐 사용하기

다음은 큐를 C++로 사용하는 방법이다. 큐는 STL에서 사용하기 편리하게 라이브러리를 제공하고 있다. C언어로도 직접 구현해서 사용할 수 있지만 알고리즘 문제를 풀때는 STL을 사용하는 것이 훨씬 편리하고 정확하기 때문에 C로 큐를 구현하진 않겠다.

위의 작동 순서를 구현해보겠다.

[ BFS를 큐로 구현하기 ]

1) 인접행렬. 그래프를 표현하는 방법

BFS를 큐로 구현하기 전에 그래프를 표현하는 방법인 인접행렬에 대해 알아보자. 인접행렬은 그래프를 표현하는 행렬을 말한다. 인접행렬에서 행은 출발노드를 의미하고 열은 도착노드를 의미한다. 그리고 노드의 개수가 n개일 때 인접행렬의 n X n의 크기를 갖는다.

예를 들어, 1번 노드와 2번 노드가 연결되어 있다면 인접행렬의 1행 2열에 1을 입력해주면 된다.

그럼 위의 바이러스 문제의 그림1을 인접행렬로 표현하면 아래와 같다.

그림1의 인접행렬

출발 - 도착	1	2	3	4	5	6	7
1		1			1
2	1		1		1
3		1
4							1
5	1	1				1
6					1
7				1

그림1은 간선에 방향이 없다. 이를 무방향 그래프라고 한다. 반대로 간선에 방향이 있는 그래프는 방향그래프라고 부른다. 무방향 그래프는 양방향으로 이동가능하기 때문에 1번 노드와 5번 노드가 연결되어 있다고 하면, 인접행렬의 1행 5열과 5행 1열을 모두 표시해주어야 한다.

2) BFS 구현하기

그림 1의 그래프를 BFS로 구현한 코드를 보면 아래와 같다.

이 코드를 위에서 설명한 큐의 동작 순서와 비교하면서 보면 더 이해하기 쉬울 것이다.

[ 단계1 ]

                     

[ 단계2 ]

     

[ 단계3 ]

       

[ 단계4 ]

                

[ 단계5 ]

              

[ 종료 ]