[C] BFS(Breadth First Search) 너비 우선 탐색

이번 글에서는 깊이 우선 탐색에 대해 집중적으로 알아보고자 한다. BFS는 정점 A에서 B로 이동하기 위해 거쳐가는 정점들의 리스트는 각기 다를 때 문어발 형식으로 나아가는 탐색 방법이다. 시작 정점에서 다음 깊이 정점을 모두 각각 방문하고 나서, 방문했던 정점을 시작으로 다시 인접 정점을 방문한다. 비유하자면, 도시의 관광명소 한 곳을 모두 들러보고 다음 관광명소로 이동하는 DFS 와는 달리, 도시의 모든 관광명소의 1층을 각각 다녀오고나서야 다시 모든 관광명소의 2층을 다녀오는 탐색 방법이다. 만약 찾고자 하는 정보가 관광명소 중 가장 낮은 층의 관광명소를 찾고자한다면, BFS가 가장 적합하다. 즉 최소거리를 보장한다는 점에서 BFS는 굉장히 효율적인 탐색방법이다. BFS는 선입선출구조를 가지고, 큐 또한 선입선출 구조를 가지기 때문에 BFS는 큐를 기반으로 구현된다.

BFS 구현 코드는 방문 정점들을 순서대로 큐에 담고, 큐에서 데이터를 하나씩 꺼내어 다음 정점을 방문하게 된다. 이 과정은 큐에 데이터가 쌓이지 않아 결국 큐가 공백이 될 때까지 진행된다. 이 과정은 while문을 통해 구현되고 for문을 통해 탐색 범위를 설정하게 된다.

#include <stdio.h>
int G[6][6];
int visit[6];			
int Q[50];
int top;
int rear; 
int D[50];
int P[50];

void BFS(int v, int V) {		
    front = -1;
    rear = -1;
    Q[++rear]=v;
    visit[v]=1;
    D[v]=0;

    while(front != rear){
        v = Q[++front];

        for(int w=1; w<=V; w++){
            if(visit[w]==0 && G[v][w]==1 ){
                visit[w]=1;
                Q[++rear]=w;
                D[w]=D[v]+1;
                P[w]=v;
            }
        }
    }
}

void BFS_d(int v, int V) {		
    front = -1;
    rear = -1;
    rear++
    Q[rear]=v;
    D[rear]=0;
    visit[v]=1;    

    while(front != rear){
        front++;
        v = Q[front];
        int d = D[front];

        for(int w=1; w<=V; w++){
            if(visit[w]==0 && G[v][w]==1 ){
                visit[w]=1;
                Q[++rear]=w;
                D[++rear]= d+1;
                P[w]=v;
            }
        }
    }
}

int main() {	
    int V, E;
	scanf("%d%d", &V, &E);

	for (int i = 0; i < E; i++) {
		int u, v;
		scanf("%d%d", &u, &v);
		G[u][v] = 1;
		G[v][u] = 1;
	}

	BFS(1, V);
}

위 예제코드에는 D 와 P 배열이 추가적으로 구성되어있다. D 배열의 경우 BFS 탐색을 수행함에 따라 지나간 정점의 깊이 정보를 담기 위해 구성되었고, P 배열의 경우 배열의 인덱스에 직전 정점의 정보를 저장함으로써 경로 정보를 저정할 수 있다. 2D 방향탐색을 위한 BFS 코드는 아래와 같다.

#include <stdio.h>
int G[10][10];
int visit[10][10];			
int Qx[100];
int Qy[100];
int top;
int rear; 
int D[100];
int P[100];
int dx = {1 -1 0 0};
int dy = {0 0 -1 1};

void BFS2(int x, int y, int n) {		
    front = rear = -1;
    rear++;
    Qx[rear]=x;
    Qy[rear]=y;
    visit[x][y]= 1;
    D[rear]=1;

    while(front != rear){
        front++;
        x = Qx[front];
        y = Qy[front];
        int d = D[front];
        for(int w=0; w<4; w++){
            int nx = x + dx[w];
            int nx = y + dy[w];
            if(visit[nx][ny]==1) continue;
            if(G[nx][ny]==0) continue;
            if(nx >=0 && nx <n && ny >=0 && ny < n ){
                visit[nx][ny]=1;
                rear++;
                Qx[rear]=nx;
                Qy[rear]=ny;
                D[rear]=s+1;
            }
        }
    } 
}

int main() {	
    int V, E;
	scanf("%d%d", &V, &E);

	for (int i = 0; i < E; i++) {
		int u, v;
		scanf("%d%d", &u, &v);
		G[u][v] = 1;
		G[v][u] = 1;
	}

	BFS(0, 0, 10);
}