[C#] 그래프 탐색 알고리즘 BFS (Breadth First Search) : 너비우선탐색

인프런 [C#, Unity] 관련 강의에서 미로찾기 게임을 구현하기 위해 DFS, BFS알고리즘을 배웠다.

정리해놓지 않으면 금방 까먹을 거 같아서 내가 이해한 식으로 정리하고 코드 기록하기!

BFS는 너비우선탐색 알고리즘으로 그래프의 모든 정점들을 한번씩 방문하면서 탐색을 하게 된다.

BFS는 예약시스템 (FIFO)을 생각하면 이해하기 쉽다. 한 정점의 간선으로 연결된 정점을 모두 Queue에 넣어서 대기시킨다. 그리고 가장 오래된 예약을 Dequeue해서 방문하고 해당 정점과 연결된 정점을 다시 Enqueue하여 예약한다.

사실 말로는 다시 기억하기 어려울거같으니 코드를 바로 넣어야겠다.

1. Graph : 그래프는 다른 선형구조처럼 클래스로 구현되어있지 않아 사용자가 편한 대로 구현하면 된다.

List <int>[] graph = new List<int>[]{
  new List<int>(){1, 3},
  new List<int>(){0, 2, 3},
  new List<int>(){1},
  new List<int>(){0, 1, 4},
  new List<int>(){3,5},
  new List<int>(){4},
}

2. BFS 함수 (DFS에서는 탐색지를 체크한 arr를 함수 바깥에 선언했지만, 이번엔 재귀함수가 아니므로 함수 내부에 선언한다.)

BFS 함수는 경로를 탐색할때, 데이터에 무엇을 담느냐에 따라 유용한 정보를 얻을 수 있다.

여기서는 parent에서 해당 노드의 이전 경로를 담고, distance에서 시작점과 해당 노드까지의 거리를 담는다.

void BFS(int start)
{
  bool[] found = new bool[6];
  int[] parent = new int[6];
  int[] distance = new int[6];

  Queue<int> que = new Queue<int>();
  que.Enqueue(start);
  parent[start] = start;
  distance[start] = 0;

  while(que.Count > 0)
  {
    int now = que.Dequeue();
    foreach(int next in graph[now]){
      if(found[next])
        continue;
      queue.Enqueue(next);
      oarent[next] = now;
      distance[next] = distance[now] + 1;
    }
  }
}

3. parent를 이용해서 목적지 노드부터 시작점 노드까지 경로 탐색하기(BFS 함수 내부에서 while문 이후)

void BFS(int start)
{
  bool[] found = new bool[6];
  int[] parent = new int[6];
  int[] distance = new int[6];

  Queue<int> que = new Queue<int>();
  que.Enqueue(start);
  parent[start] = start;
  distance[start] = 0;

  while(que.Count > 0)
  {
    //탐색로직 수행..
  }

  int dest = 5; //5번 노드가 목적지라 가정
  List<int> path = new List<int>();
  while(parent[dest] != dest)
  {
    // parent배열에서 시작점만이 자신의 부모값과 자신의 값이 같다. BGS초반에 que.Enqueue(start)참고
    path.Add(dest);
    dest = parent[dest];
  }

  // 시작점은 종료조건으로 path에 Add되지 않기 때문에 밖에서 한 번 더해준다.
  path.Add(dest);
  path.Reverse();

}