[알고리즘] 너비우선탐색(BFS) 완전정복을 향해 🤸‍♀️

참고로 풀어볼 만한 문제 모음

1. 백준 [1941] 소문난 칠공주
2. 백준[1697] 숨바꼭질

너비우선탐색(BFS)란 무엇이냐?

너비 우선 탐색은 루트 노드(혹은 다른 임의의 노드)에서 시작해서 인접한 노드를 먼저 탐색하는 방법이다.

시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 순회 방법으로 깊게(deep) 탐색하기 전에 넓게(wide) 탐색한다고 하여 너비우선탐색이라고 불린다.

너비우선탐색의 특징과 작동 원리

• BFS는 재귀적으로 동작하지 않는다.
• 그래프 탐색의 경우 어떤 노드를 방문했었는지 여부를 반드시 검사해야 한다.
• BFS는 방문한 노드를 차례로 저장한 후 꺼낼 수 있는 자료구조인 큐(Queue)를 사용한다.

깊이가 1인 모든 노드를 방문하고 나서 그 다음에 깊이가 2인 모든 노드를, 그 다음에는 깊이가 3인 모든 노드를 방문하는 식으로 계속 방문하다가 더 이상 방문할 곳이 없으면 탐색을 마친다.

위의 그림을 보면 우선
1. a 노드(시작노드)에 방문한다: 방문한 노드는 queue에 넣는다.
2. queue에서 꺼낸 노드와 인접한 노드들을 차례대로 방문한다: queue에서 방문 노드를 꺼내 해당 노드와 인접한 노드들을 1과 같은 방법으로 방문한다. 인접한 노드가 없다면 큐에서 노드를 꺼낸다.
3. queue가 empty 상태가 될 때까지 반복한다.

너비우선탐색(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. 큐의 끝에 추가
      }
    }
  }
}

너비우선탐색(BFS) 활용

너비우선탐색을 사용하는 경우는 두 노드 사이의 최단 경로 혹은 임의의 경로를 찾고 싶을 때 이 방법을 선택한다.

너비우선탐색의 시간복잡도

• 인접 리스트로 표현된 그래프 O(N+E)
• 인접 행렬로 표현된 그래프 O(N^2)

예시1
지구상에 존재하는 모든 친구 관계를 그래프로 표현한 후 Ash와 Vanessa 사이에 존재하는 경로를 찾는 경우

• 깊의 우선 탐색 - 모든 친구 관계를 다 살펴봐야 할지도 모름
• 너비 우선 탐색 - Ash와 가까운 관계부터 탐색

예시2
여러개의 블록 또는 좌표가 서로 인접한지 확인하는 경우

상세 예시1) 각 노드들이 행렬에서 인접한 관계인지 파악하기

• 참고문제 : 백준[1941] 소문난 칠공주

상세 예시2) 시작 점에서 끝 점까지 도달하는 최단 루트(시간) 구하기

• 참고문제 : 백준[1679] 숨바꼭질

너무 DP에만 매몰되어 있어서 BFS 를 쓸 거라고 생각도 못했다 😭
따지고보면 완전 BFS를 위한 문제였는데.. 아직 BFS가 익숙하지 않아서 그런거겠지
나중에 다시 풀어보자