알고리즘 : DFS와 BFS (2) - BFS (C++로 구현)

https://shine-slowly.tistory.com/48

알고리즘 : DFS와 BFS (1) - DFS (C++로 구현)

DFS에 관한 내용은 위 포스트에 있습니다.

 

참고 영상 : https://youtu.be/7C9RgOcvkvo?si=PuM-7RIBWbVPtYTw 

 

BFS (Breath-First Search, 너비우선탐색)

그래프에서 가까운 노드부터 우선적으로 탐색하는 알고리즘이다. BFS는 큐 자료구조를 이용한다.

BFS는 특정조건에서의 최단 경로를 구하는 문제에서도 많이 사용된다.

1. 탐색 시작 노드를 큐에 삽입하고 방문처리를 한다.
2. 큐에서 노드를 꺼낸 뒤에 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문처리를 한다.
3. 2번의 과정을 수행할 수 없을 때까지 반복한다.

DFS와 달리 BFS는 방문하지 않은 노드를 한 번에 큐에 삽입한다는 점이 다른 특징이다. 

 

위 그래프를 이용해서 BFS 동작 방식을 살펴보도록 하겠다. 시작 노드는 1이며 방문 기준은 번호가 낮은 인접 노드부터로 설정하였다.

 

[Step 1] 시작 노드인 '1'을 큐에 삽입하고 방문처리를 한다.

 

[Step 2] 스택의 최상단 노드인 '1'에 방문하지 않은 인접노드 '2', '3', '8'이 있다. '1'을 꺼내고 모두 큐에 삽입과 방문처리를 한다.

 

[Step 3] 큐에서 노드 '2'를 꺼내 방문하지 않은 인접 노드 '7'을 큐에 삽입하고 방문처리를 한다. (나머지는 모두 방문되어 있음)

 

[Step 4] 큐에서 노드 '3'를 꺼내 방문하지 않은 인접 노드 '4', '5'를 큐에 삽입하고 방문처리를 한다.

 

[Step 5] 큐에서 노드 '8'을 꺼내고 방문하지 않은 인접노드가 없으므로 무시한다.

 

시작노드와 가까운 순으로 탐색 순서가 설정되었음을 알 수 있다. 기업 코딩테스트에서 최단 거리 문제를 자주 출제하므로 BFS를 이해하고 있는 것이 중요하다.

 

#include<iostream>
#include<vector>
#include <queue>
using namespace std;
bool visited[9]; // 전역으로 선언하면 모두 false
vector<int> graph[9];
void bfs(int start) {
    queue<int> q;
    visited[start] = true;
    q.push(start);

    while (!q.empty()) {
        int x = q.front();
        q.pop();
        cout << x << ' ';
        
        for (int i = 0; i < graph[x].size(); i++)
        {
            if (!visited[graph[x][i]]) {// 방문하지 않았을 때
                q.push(graph[x][i]);
                visited[graph[x][i]] = true;
            }
        }
    }
}

int main() {
    // 노드 1에 연결된 노드 정보 저장
    graph[1].push_back(2);
    graph[1].push_back(3);
    graph[1].push_back(8);

    // 노드 2에 연결된 노드 정보 저장 
    graph[2].push_back(1);
    graph[2].push_back(7);

    // 노드 3에 연결된 노드 정보 저장 
    graph[3].push_back(1);
    graph[3].push_back(4);
    graph[3].push_back(5);

    // 노드 4에 연결된 노드 정보 저장 
    graph[4].push_back(3);
    graph[4].push_back(5);

    // 노드 5에 연결된 노드 정보 저장 
    graph[5].push_back(3);
    graph[5].push_back(4);

    // 노드 6에 연결된 노드 정보 저장 
    graph[6].push_back(7);

    // 노드 7에 연결된 노드 정보 저장 
    graph[7].push_back(2);
    graph[7].push_back(6);
    graph[7].push_back(8);

    // 노드 8에 연결된 노드 정보 저장 
    graph[8].push_back(1);
    graph[8].push_back(7);

    bfs(1);
}

BFS를 c++로 표현해보았다. 시작노드를 큐에 저장하고 방문처리를 해준다. 그 이휴 큐에 아무것도 남아있지 않을 때까지 반복한다.

 

 

마지막 포스팅으로 DFS, BFS를 적용한 예시 문제를 풀어볼 것이다.

DFS, BFS 내용이 이해가 됐어도 다음 포스팅을 읽어보는 것을 강력 추천한다!