C# - BFS(너비우선탐색)개념 및 코드 구현

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

시작 노드로부터 인접한 노드를 먼저 모두 방문한 후 그 인접한 노드들의 근처 노드들을 차례대로 방문하는 방식으로 동작한다.

DFS같은 경우 많은 곳에 사용되지만 BFS같은 경우 최단거리에 많이 사용된다.

1. 행렬

01 그래프 행렬로 표현

int[,] adj = new int[10, 10]
{
    {0,1,0,0,0,0,0,1,0,0 },
    {1,0,1,0,1,0,0,0,0,0 },
    {0,1,0,1,0,0,0,0,0,0 },
    {0,0,1,0,0,0,0,0,0,0 },
    {0,1,0,0,0,1,1,1,0,0 },
    {0,0,0,0,1,0,0,0,0,0 },
    {0,0,0,0,1,0,0,0,0,0 },
    {1,0,0,0,1,0,0,0,1,0 },
    {0,0,0,0,0,0,0,1,0,1 },
    {0,0,0,0,0,0,0,0,1,0 },
};

---

02 BFS알고리즘 구현

public static void BFS(int start)
{
    bool[] found = new bool[10]; // 각 정점이 방문했는지 확인

    Queue<int> q = new Queue<int>();
    q.Enqueue(start);
    found[start] = true;
   
    while (q.Count > 0)
    {
        int now = q.Dequeue();
        Console.WriteLine(now);

        for(int next = 0; next < 10; next++)
        {
            if (adj[now, next] == 0)
                continue;
            if (found[next])
                continue;
            q.Enqueue(next);
            found[next] = true;
        }
    }
}

주요 단계 설명

1) 처음 설정

q에는 방문해야할 정점을 저장한다. 처음이니까 q에 start정점을 넣고 해당 정점을 found[start]에 true를 설정한다.

Queue<int> q = new Queue<int>();
q.Enqueue(start);
found[start] = true;

2) 큐에서 현재 방문할 정점을 Dequeue

int now = q.Dequeue();
Console.WriteLine(now);

3) now가 next와 인접한지 확인

if (adj[now, next] == 0)
    continue;

4) 이미 방문한 정점인지 확인

if (found[next])
    continue;

5) 방문 표시

방문하지 않은 인접 정점인 next를 큐에 추가하고 방문한 것이므로 found[next] = true 방문 표시한다.

q.Enqueue(next);
found[next] = true;

---

결과

출력 확인

 

 

 

 

 

 

 

 

참고 :  본 내용은 MMORPG  PART2 강의를 수강하여 작성하였습니다.

https://www.inflearn.com/course/%EC%9C%A0%EB%8B%88%ED%8B%B0-mmorpg-%EA%B0%9C%EB%B0%9C-part2/dashboard