[알고리즘] 너비 우선 탐색 BFS

💡 너비 우선 탐색 DFS(Breadth First Search)란

• 그래프 탐색 방법의 한 가지
• 루트 노드 또는 임의 노드에서 인접한 노드부터 먼저 탐색하는 방법
• 깊이가 1인 모든 노드를 방문 => 깊이가 2인 모든 노드를 방문 => 깊이가 3인 모든 노드를 방문...한 후 더 이상 방문할 노드가 없으면 탐색을 마침
• 최소 비용(즉, 모든 곳을 탐색하는 것보다 최소 비용이 우선일 때)에 적합
• 동시에 움직이는 문제(토마토 썩는 문제) 해결 시 적합
• 큐를 사용하여 구현(해당 노드의 주변부터 탐색)

💡 BFS의 순서

    ① 큐에서 꺼내옴
    ② 목적지에 도달했는가?
    ③ 연결된 곳을 순회
    ④ 갈 수 있는가?
    ⑤ 체크인 & 큐에 넣음

void search(Node root) {
  Queue queue = new Queue();
  root.marked = true; // (방문한 노드 체크)
  queue.enqueue(root); // 1-1. 큐의 끝에 추가

  // 3. 큐가 소진될 때까지 계속한다.
  while (!queue.isEmpty()) {
    Node r = queue.dequeue(); // 큐의 앞에서 노드 추출
    visit(r); // 2-1. 큐에서 추출한 노드 방문
    // 2-2. 큐에서 꺼낸 노드와 인접한 노드들을 모두 차례로 방문한다.
    foreach (Node n in r.adjacent) {
      if (n.marked == false) {
        n.marked = true; // (방문한 노드 체크)
        queue.enqueue(n); // 2-3. 큐의 끝에 추가
      }
    }
  }
}

💡 관련 문제

백준 3055: 탈출

💡 BFS 신장 트리

    무향 연결 그래프에서 너비 우선 탐색(BFS)로 탐색하면서 생성된 신장 트리(Spanning Tree)

참고 링크1
참고 링크2