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

코드

---

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

/* 그래프 => 총 노드의 수: 9 (0 포함)*/
vector<int> graph[9];

void bfs(int node){
    queue<int> que; // bfs큐
    bool visited[9]; // 방문체크 

    // 첫 노드를 큐에 삽입하고, 방문표시, 출력
    que.push(node);
    visited[node] = true;
    printf("%d ", node);

    // 큐에 값이 빌 때까지 반복
    while(!que.empty()){
        // 큐에 첫번째 노드를 넣고, 삭제
        int r = que.front();
        que.pop();

        // 해당 노드의 인접노드를 탐색
        for (int i = 0; i < graph[r].size(); i++){
            int n = graph[r][i];

            // 방문하지 않은 노드라면 큐에 삽입하고, 방문표시, 출력
            if(!bfsVisited[n]) {
                que.push(n);
                visited[n] = true;
                printf("%d ", n);
            }
        }
    }
}

int main(void)
{
    /* 그래프 정의 */
    graph[0].push_back(1);

    graph[1].push_back(0);
    graph[1].push_back(2);
    graph[1].push_back(3);

    graph[2].push_back(1);
    graph[2].push_back(4);

    graph[3].push_back(1);
    graph[3].push_back(2);
    graph[3].push_back(4);
    graph[3].push_back(5);

    graph[4].push_back(2);
    graph[4].push_back(3);

    graph[5].push_back(3);
    graph[5].push_back(6);
    graph[5].push_back(7);

    graph[6].push_back(5);
    graph[6].push_back(8);

    graph[7].push_back(5);

    graph[8].push_back(6);

    bfs(0);
}

풀이

---

너비 우선 탐색(BFS)

1. 첫 노드를 큐에 삽입한다

2. 큐의 첫번째 노드의 인접노드를 탐색한다  

3. 인접노드를 큐에 삽입하고, 방문체크 +출력

4. 큐가 빌 때까지 2, 3을 반복한다