[그래프]BFS에 대하여...

안녕하세요

저번 그래프에서 기본적인 탐색방법 중 하나인 BFS에 대해 학습해보려고 합니다.

학습하기 전에 앞서 제가 저는 처음 BFS를 공부할 때 겪었던 어려움에 대해 말하고자 합니다.

저는 처음에 'BFS가 모든 노드를 방문한다는건 알겠는데 코드를 못짜겠네'라고 생각했던 적이 있습니다.

처음 공부하시는 분이시라면 저와 같은 고민을 하시는 분들이 많을 거라고 생각합니다.

그래서 저같은 경우는 BFS를 공부할 때 의사코드를 통째로 외우고 상황에 맞게 코드를 조금씩 수정하는 방식으로 공부했습니다.

개념을 알고 코드를 작성하면서 공부하다보니 BFS가 어떤 방식으로 돌아가는지(?)에 대해 저절로 알게되었습니다.

그렇기 때문에 만약, 코드 작성이 쉽지 않으시다면 의사코드를 먼저 숙지하시고 코드를 짜는 연습을 하시길 권장합니다.

+) BFS에 대한 기본 틀은 C++ 기준으로 밑에 코드를 추가해드리겠습니다.

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

너비우선탐색은 큐(Queue)를 이용하여 루트 노드를 기점으로 인접한 노드를 먼저 탐색하는 방법입니다. 

DFS와 달리 주로 최단경로를 구할 때 쓰이는 알고리즘중 하나입니다.

(가장 이해하기 쉽다고 생각되는 .gif 파일을 위키백과에서 퍼왔습니다!)

방문하는 방식은 이렇습니다.

1. 루트 노드(a)를 큐에 넣고 방문표시를 합니다.

2. 루트 노드(a)와 인접한 노드 (b), (c)를 큐에 넣고 방문표시를 합니다.

3. (b), (c)와 인접한 노드들을 큐에 넣고 방문표시를 합니다.

4. 2~3 순서를 모든 노드를 방문할때 까지 반복합니다.

#include <iostream>
#include <queue>
#include <vector>
 
using namespace std;
 
vector<int> map[1001];    //그래프의 상태를 저장할 인접리스트
bool visit[1001];    //노드의 방문 상태를 저장할 배열
 
void bfs(int start) {    //start는 처음 방문할 루트 노드 입니다.
 
    queue<int> q;
    visit[start] = true;    //루트 노드를 방문
 
    q.push(start);    //루트 노드를 q에 넣어주면서 bfs를 시작합니다.
 
 
    while (!q.empty()) {    //모든 그래프를 방문할때 까지 반복
 
        int cur = q.front(); q.pop();    //현재 큐가 가지고 있는 가장 앞 노드의 값을 반환하고 제거해줍니다.
 
        for (int i = 0; i < map[cur].size(); i++) {    //현재 노드와 인접한 모든 노드를 방문
 
            int next = map[cur][i];        //현재 방문한 노드와 인접한 노드를 반환해줍니다.
 
            if (visit[next] == false) { //만약, 그 노드가 방문하지 않은 상태라면
 
                visit[next] = true;    //방문 표시를 해주고
 
                q.push(next);    //큐에 그 노드를 넣어줍니다.
            }
        }
    }
}

---

BFS의 가장 기본적인 개념과 코드에 대해 포스팅 했습니다.

당장 생각나는것 위주로 막 쓴 게시물이라 큰 도움이 될지 모르겠습니다만,, 

추가적으로 궁금하신 사항 댓글로 남겨주시면 답변 달아드리도록 하겠습니다!

+(BFS는 나중에 다익스트라 알고리즘에 대해 학습할 때 또 쓰이기 때문에 제대로 알아두시는게 좋습니다.)