너비 우선 탐색(BFS, Breadth First Search)은 주어진 그래프의 모든 노드를 방문하기 위해 사용되는 대표적인 그래프 순회 알고리즘입니다. 이 알고리즘은 하나의 노드를 선택한 후, 해당 노드에 인접한 모든 노드를 차례대로 방문하는 방식으로 동작합니다. 인접 정점들을 모두 처리하고 나면 다음 정점으로 이동하여 같은 과정을 반복합니다.
경쟁 프로그래밍에서는 문제를 최대한 빠르게 해결해야 합니다. 따라서 C++의 STL(표준 템플릿 라이브러리)을 활용하면 BFS를 간결하고 효율적으로 구현할 수 있습니다. 이때 핵심 자료구조는 큐(Queue)입니다. 시작 정점의 인접 정점들을 큐에 추가하고, 인접 정점 처리가 끝나면 큐에서 하나의 요소를 꺼내 그 정점부터 다시 탐색을 진행합니다.
그래프에는 사이클(cycle)이 존재할 수 있기 때문에, 이미 방문한 노드를 표시하기 위한 배열을 사용해 무한 루프에 빠지지 않도록 주의해야 합니다.
입력 : 그래프의 인접 행렬 A B C D E F A 0 1 1 1 0 0 B 1 0 0 1 1 0 C 1 0 0 1 0 1 D 1 1 1 0 1 1 E 0 1 0 1 0 1 F 0 0 1 1 1 0 출력 : BFS Traversal: B A D E C F
알고리즘
bfs(vertices, start)
입력 − 정점 목록과 시작 정점
출력 − 그래프가 연결되어 있다면 모든 노드를 순회
시작
빈 큐 que 생성
처음에 모든 노드의 상태를 미방문(unvisited)으로 설정
시작 정점을 que에 삽입
que가 비어 있지 않는 동안 반복:
que에서 요소를 제거하고 u에 저장
정점 u 출력
u와 인접한 모든 정점 v에 대해:
vertices[i]가 미방문 상태라면
vertices[i]를 임시 방문 상태로 표시
v를 큐에 삽입
표시 종료
종료
u를 완전히 방문(completely visited) 상태로 표시
종료
끝
C++ 구현 예제
#include<iostream>
#include<queue>
#define NODE 6
using namespace std;
class node {
public:
int val;
int state; //방문 상태
};
int graph[NODE][NODE] = {
{0, 1, 1, 1, 0, 0},
{1, 0, 0, 1, 1, 0},
{1, 0, 0, 1, 0, 1},
{1, 1, 1, 0, 1, 1},
{0, 1, 0, 1, 0, 1},
{0, 0, 1, 1, 1, 0}
};
void bfs(node *vert, node s) {
node u;
int i, j;
queue<node> que;
for(i = 0; i<NODE; i++) {
vert[i].state = 0; //미방문
}
vert[s.val].state = 1;//방문함
que.push(s); //시작 노드 삽입
while(!que.empty()) {
u = que.front(); //큐에서 제거 후 출력
que.pop();
cout << char(u.val+'A') << " ";
for(i = 0; i<NODE; i++) {
if(graph[i][u.val]) {
//노드가 아직 방문되지 않은 경우
if(vert[i].state == 0) {
vert[i].state = 1;
que.push(vert[i]);
}
}
}
u.state = 2;//노드 u 탐색 완료
}
}
int main() {
node vertices[NODE];
node start;
char s;
for(int i = 0; i<NODE; i++) {
vertices[i].val = i;
}
s = 'B';//시작 정점 B
start.val = s-'A';
cout << "BFS Traversal: ";
bfs(vertices, start);
cout << endl;
}
실행 결과
BFS Traversal: B A D E C F
위 코드에서 각 노드의 state 값은 세 가지 단계를 나타냅니다. 0은 미방문, 1은 큐에 추가된 임시 방문 상태, 2는 탐색이 완료된 상태를 의미합니다. 이러한 상태 관리를 통해 그래프에 사이클이 있더라도 동일한 노드를 중복 방문하지 않고 효율적으로 순회할 수 있습니다.