[알고리즘] BFS와 DFS

BFS는 큐를 이용한 탐색의 한 방법으로, 너비 우선 탐색이다. 너비 우선 탐색이라고 하면 감이 잘 안 올 텐데, 알고리즘부터 보자.

1. 큐에 시작점을 push 한다.
2. 큐의 front를 저장해 두고 pop 한다. pop한 원소에 방문표시를 해둔다.
3. 저장해 둔 원소의 상하좌우 중 방문가능한 원소를 큐에 집어넣는다.
4. 큐가 빌 때까지 2~3을 반복한다.

이를 바탕으로 Flood Fill을 해보자. Flood Fill은 흔히 그림판에 있는 페인트 기능으로, 경계선을 기준으로 색을 일괄 변경하는 기능이다. 어떻게 구현하냐면, 어떤 칸의 상하좌우를 살펴보고 같은 색이라면 포함시키고, 아니라면 경계선으로 설정하는 느낌으로 구현하면 되는데 BFS를 사용하면 쉽게 구현할 수 있다.

 

BFS의 구현은 거의 정석적으로 정해져 있으니 보고 외우다시피 숙달하는 것이 좋다.

/** 탐색 BFS **/
#include <iostream>
#include <queue>
#include <algorithm>
#include <string>
#define MAX 502
using namespace std;

int board[MAX][MAX];
int visited[MAX][MAX];
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
int n, m; // n행 m열

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    queue<pair<int, int>> Q;
    cin >> n >> m;
    for (int i = 0; i < n; i++)
    {
        fill(board[i], board[i] + m, 0);
        fill(visited[i], visited[i] + m, 0);
    }

    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            cin >> board[i][j];

    visited[0][0] = 1;
    Q.push(make_pair(0, 0));

    while (!Q.empty())
    {
        pair<int, int> cur = Q.front();
        Q.pop();
        cout << "(" << cur.first << ", " << cur.second << ")\n";

        for (int i = 0; i < 4; i++)
        {
            int nx = cur.first + dx[i];
            int ny = cur.second + dy[i];
            //(nx, ny)는 cur의 상하좌우 칸이다.
            if (nx < 0 || ny < 0 || nx >= n || ny >= m)
                continue;
            if (visited[nx][ny] == 1 || board[nx][ny] == 0)
                continue;
            visited[nx][ny] = 1;
            Q.push(make_pair(nx, ny));
        }
    }
}

여기서 주의할 포인트는 상하좌우를 탐색하는 방법이다.

int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1);

for(int i=0; i<4; i++){
	int nx = cur.first + dx[i];
    int ny = cur.second + dy[i];
}

또 상하좌우 칸이 배열의 범위에 벗어나지 않는지 판단하는 부분도 중요하다.

---

DFS는 BFS와는 다른 느낌의 탐색법인데, 스택을 사용한 깊이 우선 탐색이다. 탐색 가능한 칸을 우선적으로 다 탐색하다가, 한 줄기가 끝나면 다시 시작점으로 돌아오고 이런 느낌이다. BFS는 최단 경로 문제나 Flood Fill 문제에서 사용된다. DFS는 BFS 대신 쓸 일이 없고 그래프 순회에 사용돼서 알고만 있으면 된다.

 

BFS와 관련된 아래의 문제들은 꼭 풀어보자.

[BOJ] 2178 미로탐색 - 최단 경로, BFS

 

[BOJ] C++ 7576 토마토 - 시작점이 여러 개인 최단 경로, BFS

 

[BOJ] C++ 4179 불! - 두 종류의 시작점을 포함한 최단경로, BFS