너비 우선 탐색 (BFS)

개념

• 탐색할 때 너비를 우선으로함 → 두 노드 사이의 최단경로 or 임의의 경로를 찾고 싶을 때 사용
  • 시작(root node)에서 인접한 노드를 먼저 탐색하고, 멀리 떨어진 node는 나중에 방문하는 탐색 방법
  • 깊게 탐색 전, 넓게 탐색
  • 노드 방문 여부에 대해 반드시 검사해야함 (노드 방문 후 처리)
• Queue를 사용 → FIFO (First In First Out)
• 먼저 들어온 것 → 먼저 처리

풀이

1. 시작노드 (Start Node) → Queue에 삽입 + 방문처리
2. ( 2 ~ N )
3. 큐에서 하나의 노드를 꺼냄
4. 꺼낸 노드에 연결된 노드 중 방문하지 않은 노드 방문 & 차례대로 큐에 삽입

코드

#include <iostream>
#include <queue>
#include <vector>
using namespace std;

// 원소의 갯수
int number = 7; 
// 방문처리
int checked[7];
// 그래프의 연결 관계를 인접리스트로 저장  
vector<int> adj[7];

/* 

    1. 시작노드 Queue에 삽입 and 방문처리
    2.
     1. 큐에서 하나의 노드를 꺼냄
     2. 꺼낸 노드에 연결된 노드 중 방문하지 않은 노드 방문 & 차례대로 큐에 삽입

 */

void bfs(int start) {
    queue<int> q;
    q.push(start); // 시작노드 삽입
    checked[start] = true; // 방문처리
    while(!q.empty()) {
        // 1) 큐에서 노드 꺼냄
        int now = q.front();
        q.pop();
        // 2) 현재 노드에서 인접한 모든 노드들 중
        for(int i=0;i<adj[now].size();i++) {
            int adjNode = adj[now][i];
            // 아직 방문하지 않은 노드 (adjNode) queue에 push
            if(checked[adjNode] == 0) {
                q.push(adjNode);
                checked[adjNode] = 1;
            }
        }
    }
}

참고 ① - 나동빈님 강의
참고 ②