안녕하세요. 김용성입니다.
오늘 포스팅은 어제 말씀드렸던대로 너비우선탐색 BFS를 설명드리는 시간을 가지도록 하겠습니다.

BFS

DFS가 깊이 우선 탐색이었다면 BFS(Breadth-First-Search)는 번역 그대로 '너비 우선 탐색'입니다.

BFS는 굉장히 일반적인 사고방식입니다. 나로부터 가까운 녀석들을 우선적으로 탐색하고, 그 이후에는 탐색한 녀석들로부터 가까운 녀석들을 탐색하는 식으로 탐색을 진행하죠. 저는 이러한 방식을 '코로나' 같다고 생각해요. 코로나는 주변사람들에게 퍼지고, 또 그 주변사람들의 주변사람들에게 퍼져나가죠? 그렇게 이해하시면 쉽게 이해할 수 있습니다.

탐색 순서는 0->1->2->3->4->5->6입니다. 시작 정점으로부터 가까운 정점을 먼저 방문하고, 멀리 떨어져 있는 정점을 나중에 방문하는 순회 방법이죠.
어제 설명드린 DFS가 스택을 사용한다면 BFS는 큐를 사용하여 구현할 수 있습니다. 가까운 거리에 있는 정점들을 차례로 담은 뒤 차례대로 꺼낼 수 있는 자료형이기 때문이죠.
위 그림의 순서가 어떻게 작동하는지 설명드리도록 하겠습니다.

순환 과정

1, 0번 정점에 대한 탐색을 수행합니다.
2, 0번 정점과 인접해있는 1,2번을 실행 순서에 넣습니다.
3, 1번 정점에 대한 탐색을 수행한 뒤 1번 정점과 연결되어 있는 3,4 정점을 실행 순서에 넣습니다.
4, 2번 정점에 대한 탐색을 수행한 뒤 2번 정점과 연결되어 있는 5,6 정점을 실행 순서에 넣습니다.
5, 3번 정점에 대한 탐색을 수행합니다.
6, 4번 정점에 대한 탐색을 수행합니다.
7, 5번 정점에 대한 탐색을 수행합니다.
8, 6번 정점에 대한 탐색을 수행합니다.
9, 탐색을 마쳤습니다.

그렇다면 이 과정을 한번 큐의 FIFO 성질을 통해서 나타내보도록 할까요?

[] // 빈 큐
[0] // 0 삽입
[1,2] // 0을 popleft한 후 인접 정점 1,2 삽입
[2,3,4] // 1을 popleft한 후 인접 정점 3,4 삽입
[3,4,5,6] // 2를 popleft한 후 인접 정점 5,6 삽입
[4,5,6] // 3을 popleft
[5,6] // 4를 popleft
[6] // 5를 popleft
[] // 빈큐: 탐색 종료

왜 BFS가 큐와 관련이 있는지 감이 오시나요?

BFS 또한 DFS때와 마찬가지로 visited라는 배열을 이용하여 구현을 할 수 있습니다.
저번과 같이 0=> 방문하지 않음, 1=> 방문함 이라고 표현하기로 약속을 하도록 하겠습니다.

BFS 알고리즘

BFS의 알고리즘은 다음과 같습니다.

bfs(v):
  
   v를 방문되었다고 표시; //visited 배열 활용
   큐 Q에 정점 v 삽입;
   while(Q가 공백이 아니면) do
      Q에서 정점 w를 삭제;
      for all u가 w에 인접한 정점인 동안 do
         if(u가 아직 방문되지 않았다면)
            then u를 큐에 삽입;
                 u를 방문되었다고 표시;
   

무조건 큐에서 정점을 꺼내서 정점을 방문하고 인접정점들을 큐에 추가합니다. 이러한 동작은 큐에 아무 내용이 존재하지 않을 때까지 반복하는 것이죠.

BFS 동작 코드

이번에는 위 의사 코드를 C언어 코드로 구현해보도록 하겠습니다.

void bfs_mat(GraphType* g,int v){
   int w;
   QueueType q;
   
   queue_init(&q);
   visited[v]=TRUE;
   printf("visited %d->",v);
   enqueue(&q,v);
   while(!is_empty(&q)){
      v=dequeue(&q);
      for(w=0;w<g->n;w++)
         if(g->adj_mat[v][w]&&!visited[w]){
             visited[w]=TRUE;
             printf("visited %d->",v);
             enqueue(&q,w);
         }       
   }
}

설명

일단 큐는 구조체로 정의해 놓은 채로 bfs 동작함수 내에서 초기화를 시켜주었습니다.
주의해야할 점은 매개변수로 들어온 변수 v와 while문에서 동작하는 v는 서로 다른 녀석이라는 점입니다. (이부분에 대해서는 printf문의 모양을 통일화 시키기 위해 이런식으로 작성하였습니다.)
while문 내부의 v는 queue에서 제외한 요소를 할당해주는 녀석입니다.

C로 큐를 만들자
만약 큐를 사용하는 방법에 대해 어려움을 겪고계신 분들은 해당 링크의 포스팅을 참고해주시면 좋을 것 같습니다!

BFS 전체 코드

#include <stdio.h>
#include <stdlib.h>

#define TRUE 1
#define FALSE 0
#define MAX_QUEUE_SIZE 10

typedef int element;
typedef struct{
    element queue[MAX_QUEUE_SIZE];
    int front,rear;
} QueueType;

void error(char *message){
    fprintf("stderr",message);
    exit(1);
}

void queue_init(QueueType *q){
    q->front=q->rear=0;
}

int is_empty(QueueType *q){
    return (q->front==q->rear);
}

int is_full(QueueType *q){
    return ((q->rear+1)%MAX_QUEUE_SIZE==q->front);
}

void enqueue(QueueType *q,element item){
    if(is_full(q))
        error("overflow");
    q->rear=(q->rear+1)%MAX_QUEUE_SIZE;
    q->queue[q->rear]=item;
}

element dequeue(QueueType *q){
    if(is_empty(q))
        error("underflow");
    q->front=(q->front+1)%MAX_QUEUE_SIZE;
    return q->queue[q->front];
}

#define MAX_VERTICES 50

typedef struct GraphType{
    int n;
    int adj_mat[MAX_VERTICES][MAX_VERTICES];
} GraphType;
int visited[MAX_VERTICES];

void graph_init(GraphType* g){
    int r,c;
    g->n=0;
    for(r=0;r<MAX_VERTICES;r++)
        for(c=0;c<MAX_VERTICES;c++)
            g->adj_mat[r][c]=0;
}

void insert_vertex(GraphType* g,int v){
    if((g->n)+1>MAX_VERTICES) {
        fprintf(stderr,"overflow");
        return;
    }
    g->n++;
}

void insert_edge(GraphType* g,int start,int end){
    if(start>=g->n||end>=g->n){
        fprintf(stderr,"graph index error");
        return;
    }
    g->adj_mat[start][end]=1;
    g->adj_mat[end][start]=1;
}

void bfs_mat(GraphType* g,int v){
    int w;
    QueueType q;

    queue_init(&q);
    visited[v]=TRUE;
    printf("visit %d->",v);
    enqueue(&q,v);
    while(!is_empty(&q)){
        v=dequeue(&q);
        for (w=0;w<g->n;w++)
            if(g->adj_mat[v][w]&&!visited[w]){
                visited[w]=TRUE;
                printf("visited %d->",w);
                enqueue(&q,w);
            }
    }
}

int main(void){
    GraphType *g;
    g=(GraphType *)malloc(sizeof(GraphType));
    graph_init(g);
    for(int i=0;i<7;i++)
        insert_vertex(g,i);

    insert_edge(g,0,1);
    insert_edge(g,0,2);
    insert_edge(g,1,3);
    insert_edge(g,1,4);
    insert_edge(g,2,5);
    insert_edge(g,2,6);

    printf("BFS\n");
    bfs_mat(g,0);
    printf("\n");
    free(g);
    return 0;

}

출력 결과
...
BFS
visit 0 -> visit 1 -> visit 2 -> visit 3 -> visit 4 -> visit 5 -> visit 6 ->

가장 상단에서 그림으로 나타내었던 트리를 그래프로 구현하였으며, 저희가 예상한대로 잘 동작함을 확인할 수 있습니다.

마무리

어제 오늘 포스팅을 통해서 BFS/DFS에 대해 어느정도 정리를 해보았는데요.
한번에 이해가 되시는 분들도 있을 거예요. 그 분들을 존경합니다.ㅎㅎ
저는 여러번 읽고 또 읽고, 외우다시피 했어도, 이를 통해서 코딩테스트 문제를 풀 때는 틀리곤 합니다.😔
내용이 어렵게 느껴지셔도 그것은 당연한 것이니 너무 염려하지 않으셔도 됩니다.
그런 분들은 절망하지 말고 코드를 한번 직접 작성해보시며 분석해보는 것을 추천드려요.
포스팅 읽어주셔서 정말 감사합니다. :)