[자료구조] BFS(너비 우선 탐색)

 

BFS(Breadth First Search, 너비 우선 탐색)

• 다차원 배열에서 각 칸을 방문할 때 너비를 우선으로 방문하는 알고리즘 
• 그래프 자료구조에서 모든 노드를 방문하기 위한 알고리즘 
• 그래프 = 정점과 간선으로 이루어진 자료구조

 

 

BFS 구현

다차원 배열로 BFS를 구현해보자. 

 

다차원 배열 BFS 구현에 필요한 것들이다. 

• 좌표를 담을 큐
• 방문해야 할 곳을 담은 다차원 배열 ( board[x,y] )
• 방문했던 곳을 저장하는 다차원 배열 ( visit[x, y] )
• 상하좌우 좌표 배열 ( dx[4], dy[4] )

 

구현 방법 

1. 방문해야 하는 칸을 큐에 넣는다. 방문했다는 표시를 bool배열에 남긴다. 
2. 큐에서 원소를 꺼내고 해당 칸에서 상하좌우로 인접한 칸에 대해 3번 과정을 진행한다. 
3. 처음 해당 칸을 방문했다면 방문했다는 표시를 bool배열에 남기고 해당 칸을 큐에 삽입한다. 
   해당 칸을 이전에 방문했다면 아무것도 하지 않는다. 
4. 큐가 빌 때까지 2번 과정을 반복한다. 

 

시간 복잡도

방문해야 하는 칸은 큐에 1번씩 들어간다. 최악의 경우 방문해야 하는 칸이 N개라면 시간 복잡도는 O(N)이다. 

 

 

코드

using System.Text;

namespace BFS
{
    internal class BFS구현
    {
        static int[,] board = new int[,] // 0 : 빨강칸, 1 : 파랑칸
        {
            {1,1,1,0,1,0,0,0,0,0},
            {1,0,0,0,1,0,0,0,0,0},
            {1,1,1,0,1,0,0,0,0,0},
            {1,1,0,0,1,0,0,0,0,0},
            {0,1,0,0,0,0,0,0,0,0},
            {0,0,0,0,0,0,0,0,0,0},
            {0,0,0,0,0,0,0,0,0,0}
        };
        static bool[,] visit = new bool[502, 502]; // 방문 여부 저장 (0 : 방문 X, 1 : 방문 O)

        const int N = 7;
        const int M = 10;

        static int[] dx = { 1, 0, -1, 0 };
        static int[] dy = { 0, 1, 0, -1 };

        static void Main(string[] args)
        {
            Queue<(int x, int Y)> queue = new Queue<(int X, int Y)>();
            StringBuilder sb = new StringBuilder();

            visit[0, 0] = true; // 방문 표시 남기기
            queue.Enqueue((0, 0)); // 해당 칸을 큐에 넣기 

            // 큐가 빌 때까지 큐의 front를 빼고 해당 좌표의 상하좌우
            // 를 살펴보면서 큐에 넣어주는 작업을 반복한다. 
            // 파란색 칸이면서 아직 방문하지 않은 칸에 넣는다. 

            while(queue.Count > 0)
            {
                // front 빼기 
                (int X, int Y) cur = queue.Dequeue();
                sb.Append($"({cur.X}, {cur.Y}) -> ");

                // 상하좌우 확인 후, 큐에 넣기 (파란색 칸이면서 아직 방문하지 않았다면)
                for(int dir = 0; dir < 4; dir++)
                {
                    // 상하좌우 좌표 구하기. 
                    int nx = cur.X + dx[dir];
                    int ny = cur.Y + dy[dir];

                    // 인덱스 범위에서 벗어나거나, 이미 방문한 칸이거나, 빨강칸이면
                    // 다음 좌표 검사하기.
                    if (nx < 0 || nx >= N || ny < 0 || ny >= M) continue;
                    if (visit[nx, ny] || board[nx, ny] != 1) continue;

                    visit[nx, ny] = true; // 방문했음을 표시
                    queue.Enqueue((nx, ny)); // 
                }
            }

            Console.WriteLine(sb.ToString());
        }
    }
}

 

 

cf)

바킹독 실전 알고리즘 BFS