[알고리즘] 넓이 우선 탐색(BFS)

넓우선탐색(Breadth-First Search, BFS)란?

• 넓이 우선 탐색(Breadth-First Search, BFS)은 그래프 탐색 알고리즘 중 하나로, 루트 노드에서 시작해서 인접한 노드를 먼저 모두 탐색한 후에, 그 인접한 노드들을 시작점으로 다시 인접한 노드를 모두 방문하는 방법이다.

 

BFS의 원리

BFS는 큐(Queue) 자료구조를 이용하여 구현할 수 있다. 큐에 먼저 시작 노드를 넣고, 해당 노드와 인접한 모든 노드들을 큐에 추가한다. 그리고 큐에서 하나씩 노드를 빼서 그 노드와 인접한 노드들을 다시 큐에 추가한다. 이 과정을 큐가 빌 때까지 반복하면 된다. 큐를 이용하기 때문에 먼저 들어온 것이 먼저 처리되기 때문에 넓이 우선 탐색이라고 부른다.

 

BFS는 최단 경로 탐색 등에 자주 사용됩니다. 또한, 미로 찾기와 같은 문제에서도 사용할 수 있습니다. 단점으로는 BFS는 깊이 우선 탐색(DFS)에 비해 탐색하는 노드의 수가 많아지기 때문에, 탐색 속도가 느리다는 점이 있습니다.

 

넓이 우선 탐색(BFS)

• C언어

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
typedef int ElementType;

typedef struct tagNode
{
    ElementType Data;
} Node;

typedef struct tagCircularQueue
{
    int   Capacity;
    int   Front;
    int   Rear;

    Node* Nodes;
} CircularQueue;

void        CQ_CreateQueue(CircularQueue** Queue, int Capacity);
void        CQ_DestroyQueue(CircularQueue* Queue);
void        CQ_Enqueue(CircularQueue* Queue, ElementType Data);
ElementType CQ_Dequeue(CircularQueue* Queue);
int         CQ_GetSize(CircularQueue* Queue);
int         CQ_IsEmpty(CircularQueue* Queue);
int         CQ_IsFull(CircularQueue* Queue);
int         CQ_Front(CircularQueue* Queue);
int         CQ_Back(CircularQueue* Queue);


void  CQ_CreateQueue(CircularQueue** Queue, int Capacity)
{
    //  큐를 자유 저장소에 생성 
    (*Queue) = (CircularQueue*)malloc(sizeof(CircularQueue));

    //  입력된 Capacity+1 만큼의 노드를 자유 저장소에 생성 
    (*Queue)->Nodes = (Node*)malloc(sizeof(Node) * (Capacity + 1));

    (*Queue)->Capacity = Capacity;
    (*Queue)->Front = 0;
    (*Queue)->Rear = 0;
}

void CQ_DestroyQueue(CircularQueue* Queue)
{
    free(Queue->Nodes);
    free(Queue);
}

void CQ_Enqueue(CircularQueue* Queue, ElementType Data)
{
    int Position = 0;

    if (Queue->Rear == Queue->Capacity)
    {
        Position = Queue->Rear;
        Queue->Rear = 0;
    }
    else
        Position = Queue->Rear++;

    Queue->Nodes[Position].Data = Data;
}

ElementType CQ_Dequeue(CircularQueue* Queue)
{
    int Position = Queue->Front;

    if (Queue->Front == Queue->Capacity)
        Queue->Front = 0;
    else
        Queue->Front++;

    return Queue->Nodes[Position].Data;
}

int CQ_GetSize(CircularQueue* Queue)
{
    if (Queue->Front <= Queue->Rear)
        return Queue->Rear - Queue->Front;
    else
        return Queue->Rear + (Queue->Capacity - Queue->Front) + 1;
}

int CQ_IsEmpty(CircularQueue* Queue)
{
    return (Queue->Front == Queue->Rear);
}
int CQ_IsFull(CircularQueue* Queue)
{
    if (Queue->Front < Queue->Rear)
        return (Queue->Rear - Queue->Front) == Queue->Capacity;
    else
        return (Queue->Rear + 1) == Queue->Front;
}
int CQ_Front(CircularQueue* Queue)
{
    return Queue->Nodes[Queue->Front].Data;
}
int CQ_Back(CircularQueue* Queue)
{
    return Queue->Nodes[Queue->Rear - 1].Data;
}
int n = 5;
int visited[100];
int list[100][100];

void bfs(int v) {
    CircularQueue* queue = NULL;
    CQ_CreateQueue(&queue, 5);
    CQ_Enqueue(queue,v);
    visited[v] = true;
    printf("%d\n", v);
    while (CQ_IsEmpty(queue)) {
        int temp = CQ_Dequeue(queue);
        for (int i = n-1; i >= 0; i--) {
            if (list[temp][i] && !visited[i]) {
                CQ_Enqueue(queue, i);
                printf("%d\n", i);
            }
        }
    }
}
int main(void) {
    n = 5;
    list[0][1] = 1;
    list[0][2] = 1;
    list[1][0] = 1;
    list[1][2] = 1;
    list[1][3] = 1;
    list[1][4] = 1;
    list[2][0] = 1;
    list[2][1] = 1;
    list[3][1] = 1;
    list[4][1] = 1;

    //노드 방문
    for (int i = 0; i < n; i++) {
        if (!visited[i]) {
            bfs(i);
        }
    }
}

• C#

using System;
using System.Collections.Generic;

namespace yongyong2
{
    internal class Program
    {
        static int N;
        static int[,] Map;
        static bool[] dfsbool;
        static bool[] bfsbool;

        static void Main(string[] args)
        {
            string[] input1 = Console.ReadLine().Split();
            N = int.Parse(input1[0]);
            int M = int.Parse(input1[1]);
            int V = int.Parse(input1[2]);

            Map = new int[N + 1, N + 1];
            bfsbool = new bool[N + 1];

            for (int i = 0; i < M; i++)
            {
                string[] input2 = Console.ReadLine().Split();
                int temps = int.Parse(input2[0]);
                int tempe = int.Parse(input2[1]);
                Map[temps, tempe] = 1;
                Map[tempe, temps] = 1;
            }


            BFS(N, V);
        }

        public static void BFS(int N, int V)
        {
            Queue<int> queue = new Queue<int>();
            queue.Enqueue(V);
            bfsbool[V] = true;
            Console.Write(V + " ");

            while (queue.Count > 0)
            {
                int temp = queue.Dequeue();

                for (int i = 1; i < N + 1; i++)
                {
                    if (Map[temp, i] == 1 && bfsbool[i] == false)
                    {
                        queue.Enqueue(i);
                        Console.Write(i + " ");
                        bfsbool[i] = true;
                    }
                }
            }
        }
    }
}

예제 문제

[C#]백준 1260번: DFS와 BFS

 

 

[C#]백준 24444번: 알고리즘 수업 - 넓이 우선 탐색 1