BFS 알고리즘

점점 알고리즘을 풀 일이 더 많아지면서,

이제 구글링을 하지 않고 내 블로그를 보면서 공부하기 위해 정리하는 알고리즘 포스트! (서론이 길다 🐶)

 

알고리즘 중에서도 정말 중요하고, 많은 문제를 해결할 수 있는 BFS 알고리즘이 첫번째 알고리즘 포스팅이닷

 

 

-

 

BFS (Breath-First Search)

BFS는 너비 우선 탐색 즉, 루트 노드에서 시작해서 인접한 노드를 먼저 탐색하는 알고리즘이다.

앞만 보고 직진하는 DFS(Depth-First Search)와 비교하면 천천히 탐색하면서 세력을 넓혀가는 느낌이랄까..?

BFS는 빨간색 - 주황색 - 노란색 - 초록색 순으로 탐색이 진행된다.

DFS는 BFS와 달리 앞만 보고 질주한다. ㅋㅋ 

 

 

 

이 알고리즘을 사용해야하는 문제는?

두 노드 사이의 최단 경로 혹은 임의의 경로를 찾고 싶을 때 많이 사용한다.

 

 

문제 예시

백준 - 1697번 숨바꼭질

https://www.acmicpc.net/problem/1697

1697번: 숨바꼭질

백준 - 14502번 연구소

https://www.acmicpc.net/problem/14502

14502번: 연구소

 

 

특징

- BFS는 DFS와 달리 재귀적으로 동작하지 않는다

- 어떤 노드를 방문했었는지 반드시 검사해야한다.

- 프로그래밍할 때 Queue를 사용한다.

- Prim, Dijkstra 알고리즘과 유사하다! -> 얘네도 나중에 포스팅 하겠다.

 

 

 

동작 과정

(1)

시작 노드부터 탐색을 시작한다.

- queue에 시작 노드를 push

* queue에는 탐색해야 할 노드를 push하는 것!

 

 

(2)

시작 노드와 연결된 노드로 이동한다.

특정 노드와 연결된 노드로 이동하려면 특정 노드는 queue에서 pop해서 current에 저장한다.

* 탐색이 끝나면 pop!

그리고 다음 노드로 이동한다. (이 예시에서는 여러개의 노드가 연결되어 있으면 값이 더 작은 노드로 이동하겠다.)

 

(3)

current와 연결된 노드가 여러개라면 연결된 노드를 모두 탐색한다.

 

(4)

 

(5)

(6)

current에 연결된 노드를 모두 탐색했으므로 queue front에 있는 노드를 pop해서 다시 current에 저장한다.

1에 연결된 0, 2 는 모두 방문했던 노드이므로 탐색을 하지 않는다.

 

(7)

탐색할 노드가 없으므로 queue front에 있는 노드를 pop해서 current에 저장한다.

2에 연결된 3은 방문하지 않았던 노드이므로 queue에 3을 push한다.

 

(8)

 

(9)

queue가 empty 상태가 되면 모든 노드의 탐색이 끝난 것이므로 탐색을 종료한다.

 

(10)

 

 

 

 

 

 

 

 

 

 

방문 순서는 0, 1, 2, 4, 3 이다.

 

 

 

 

정리

순서를 정리하면 다음과 같다.

 

1) 시작 노드를 queue에 push

2) 시작 노드를 pop하고 current에 저장

3) current에 연결된 노드를 순서대로 queue에 push

4) 더 이상 연결된 노드가 없다면 pop해서 current에 저장

5) queue가 empty일 때까지 3), 4) 반복

 

 

 

소스 코드

C++로 작성한 코드는 다음과 같다.

N: 노드의 개수

V: 노드의 값

vector<int> graph[1001];

void bfs(){
    bool *visited = new bool[N+1];
    fill_n(visited, N+1, false);
    queue <int> q;

    q.push(V);
    visited[V] = true;

    while(!q.empty()){

        int current = q.front();
        cout << current << " ";
        q.pop();

        for(int i = 0; i < graph[current].size(); i++) {
            int node = graph[current][i];
            if (!visited[node]) {
                q.push(node);
                visited[node] = true;
            }
        }
    }
}

 

 

포스팅 내용에 문제가 있다면, 언제나 태클 감사합니다~