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

정의

특징

• 시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 순회 방법

• 깊게(deep) 탐색하기 전에 넓게(wide) 탐색하는 것

• 너비 우선 탐색(BFS)이 깊이 우선 탐색(DFS)보다 좀 더 복잡

• 직관적이지 않은 면이 있다.
• BFS는 시작 노드에서 시작해서 거리에 따라 단계별로 탐색한다고 볼 수 있다.

• 재귀적으로 동작하지 않는다.

• 그래프 탐색의 경우 어떤 노드를 방문했었는지 여부를 반드시 검사 해야 한다는 것이다.
• 이를 검사하지 않을 경우 무한루프에 빠질 위험이 있다.

• BFS는 방문한 노드들을 차례로 저장한 후 꺼낼 수 있는 자료 구조인 큐(Queue)를 사용
• 선입선출(FIFO) 원칙으로 탐색
• 일반적으로 큐를 이용해서 반복적 형태로 구현하는 것이 가장 잘 동작한다.

시간복잡도

• 인접 리스트로 표현된 그래프: O(N+E)

• 인접 행렬로 표현된 그래프: O(N^2)

• 깊이 우선 탐색(DFS)과 마찬가지로 그래프 내에 적은 숫자의 간선만을 가지는 희소 그래프(Sparse Graph) 의 경우 인접 행렬보다 인접 리스트를 사용하는 것이 유리

예시

• ‘Prim’, ‘Dijkstra’ 알고리즘과 유사

• 두 노드 사이의 최단 경로 혹은 임의의 경로를 찾고 싶을 때
• 지구상에 존재하는 모든 친구 관계를 그래프로 표현한 후 A와 B 사이에 존재하는 경로를 찾는 경우
• 깊이 우선 탐색의 경우 - 모든 친구 관계를 다 살펴봐야 할수도 있음
• 너비 우선 탐색의 경우 - A와 가까운 관계부터 탐색

과정

1. a 노드(시작 노드)를 방문한다. (방문한 노드 체크)
1. 큐에 방문된 노드를 삽입(enqueue)한다.
2. 초기 상태의 큐에는 시작 노드만이 저장
1. 즉, a 노드의 이웃 노드를 모두 방문한 다음에 이웃의 이웃들을 방문한다.

2. 큐에서 꺼낸 노드과 인접한 노드들을 모두 차례로 방문한다.
1. 큐에서 꺼낸 노드를 방문한다.
2. 큐에서 커낸 노드과 인접한 노드들을 모두 방문한다.
1. 인접한 노드가 없다면 큐의 앞에서 노드를 꺼낸다(dequeue).
3. 큐에 방문된 노드를 삽입(enqueue)한다.

3. 큐가 소진될 때까지 계속한다.

구현

Grid

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

using namespace std;

vector<vector<int>> map;
int visited[101][101] = {0, };
int m, n;
int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};

int bfs() {
    queue<pair<int, int>> q;
    q.push({0, 0});

    while (q.size() > 0) {
        pair<int, int> p = q.front();
        q.pop();

        int x = p.first;
        int y = p.second;

        for (int i = 0; i < 4; ++i) {
            int nx = x + dx[i];
            int ny = y + dy[i];

            //벽에 닿으면, 반복문 끝
            if (ny >=m || nx >= n || ny < 0 || nx < 0) {
                continue;
            }

            //안가봤고, 갈 수 있는 곳이면
            if (visited[ny][nx] == 0 && map[ny][nx] == 1) {
                //방문 기록
                visited[ny][nx] = visited[y][x] + 1;
                q.push({nx, ny});
            }
        }
    }

    return visited[m - 1][n - 1];
}

int main()
{
    vector<vector<int>> maps = {{1,0,1,1,1}, {1,0,1,0,1}, {1,0,1,1,1}, {1,1,1,0,1}, {0,0,0,0,1}};

    visited[0][0] = 1;

    m = maps.size();
    n = maps[0].size();

    map = maps;

    int answer = bfs();

    if (answer == 0) {
        cout << -1;
    } else {
        cout << answer;
    }
}

Graph