[BFS] 너비 우선 탐색

DFS (깊이 우선 탐색)과도 엮이는 부분이 많을 수밖에 없습니다.

다만, DFS는 이 글에서 다루지 않으며 BFS에 대해서만 다룹니다. DFS는 나중에 별도의 글로 다루겠습니다.

큐를 배울 때 스택을 같이 배우듯, BFS를 배울 때 DFS를 일반적으로 같이 배워두는 게 좋습니다.

맞은 사람을 기준으로 보면, BFS의 기본 문제는 "[1260] DFS와 BFS"인것 같지만

이글에서는 BFS를 몇가지 형태로 분류하여, 각 분류를 대표하는 형태의 문제를 몇 개 선별해두었습니다.

 

 

※ 하나의 스타일에 여러개의 특정한 형태가 포함되도록 유형화했습니다.

※ 최소 한문제 이상의 연관된 문제를 BOJ에서 수록했으며, "[문제번호] 문제이름"의 형태입니다.

※ 주소창에 "boj.kr/문제번호"로 간단히 문제로 넘어갈 수 있습니다.

 

<0> 기본 구현

[2178] 미로탐색을 해결하는 코드를 아래에 첨부합니다.

2차원 배열에서 (1,1) -> (N,M)까지 도달하는 최단거리를 구해야하는 문제이며,

입력되는 배열에는 장애물과 빈칸, 두가지형태가 존재합니다.

#include <bits/stdc++.h>
using namespace std;
typedef struct {
    int y, x, turn;
} state;  //(y,x) <-> (R,C)
int Map[101][101], dy[4] = {0, 1, 0, -1}, dx[4] = {1, 0, -1, 0};
int n, m;  // maxRow,maxColumn of map
void input(void) {
    cin >> n >> m;
    string temp;
    for (int i = 0; i < n; i++) {
        cin >> temp;
        for (int j = 0; j < m; j++) {
            Map[i][j] = temp[j] - '0';  // string -> int
        }
    }
    return;
}
void bfs(int startY, int startX) {
    // init
    queue<state> q;
    q.push({startY, startX, 1});  // default turn is 1, including (1,1)
    bool visited[101][101];
    memset(visited, 0, sizeof(visited));
    visited[startY][startX] = true;
    // search
    while (!q.empty()) {
        state cur = q.front();
        q.pop();
        // check answer
        if (cur.y == n - 1 && cur.x == m - 1) {
            cout << cur.turn;
            return;
        }
        for (int i = 0; i < 4; i++) {
            int nextY = cur.y + dy[i];
            int nextX = cur.x + dx[i];
            if (nextY < 0 || nextX < 0 || startY >= n || startX >= m)
                continue;  // out of bound
            if (Map[nextY][nextX] == 1 && visited[nextY][nextX] == false) {
                q.push({nextY, nextX, cur.turn + 1});
                visited[nextY][nextX] = true;
            }
        }
    }
}
int main(void) {
    input();
    bfs(0, 0);
    return 0;
}

방향데이터

dy[], dx[]는 방향데이터입니다. 문제마다 얼마든지 달라질 수 있지만, 변형되어도 응용하기 가장 쉽습니다.

위 코드는 3시를 시작으로 시계방향으로 4방향을 구현했지만,  자기가 편한 대로 쓰면 됩니다.

다만 시계방향이든, 반시계 방향이든 하나로 정해야 실수할 일이 적긴 할 겁니다.

 

입력

입력을 받을 때 인덱스를 0부터 받고 와 1부터 받고는 당연히 자기 취향입니다.

(공간복잡도가 O(N)이 O(N+1)로 늘어나 봤자입니다, 아무 상관없습니다)

string으로 입력이 주어질 때, int로 변환할지 말지도 자기 취향입니다.

위 코드는 0부터 시작하는 int배열로 변환하여 입력을 받았습니다.

 

BFS의 구현

queue<state> q;
q.push({startY, startX, 1});  // default turn is 1, including (1,1)
bool visited[101][101];
memset(visited, 0, sizeof(visited));
visited[startY][startX] = true;

bfs에서 init은 문제마다 다르지만, 대부분 시작점을 queue에 push 하고 방문 처리하는 것은 공통입니다.

"정답이 나올 때까지" 탐색해야 하므로, while()을 사용하여 구현하는 것이 편리합니다.

BFS의 탐색 중의 구성은 크게는 2가지인데, "정답 판별"과 "다음 정점 push"입니다.

다만 이를 하기 전에 현재 정점을 꼭 pop()해주어야 합니다.

 

queue에 들어갈 원소는 <int>가 될 수도 있고, pair <int, int>처럼 2개씩 관리해도 됩니다.

2개보다 더 많은 원소를 한 번에 관리한다면, struct를 사용하는 것이 편리합니다만,

3개나 4개 정도라면 pair <int, pair <int, int>>나 pair <pair <int, int>, pair <int, int>>처럼 사용해도 됩니다.

구조체와 별개로 c++의 tuple을 사용하는 방법도 있습니다.

위 코드는 struct를 이용해 {행, 열, 거리}를 queue의 원소로 구성했습니다.

 

정답 판별

탑-다운 dp/백트래킹에서 사용했던 기저 사례와 유사합니다.

if (cur.y == n - 1 && cur.x == m - 1) {
    cout << cur.turn;
    return;
}

정답이 아니라면, 별도로 처리해주어야 할 것은 없습니다.

 

다음 정점 탐색

가장 먼저 할 일은, 2차원 배열에서 다음 위치, 즉 행과 열을 알아내야 하는 일입니다.

앞서 구성한 방향 데이터를 활용하여 아래처럼 작성할 수 있습니다.

int nextY = cur.y + dy[i];
int nextX = cur.x + dx[i];

 

당연한 말이지만, 행은 행끼리 연산해야 하고, 열은 열끼리 연산해야 합니다.

어처피 dy[]나 dx[]에는 +1, 0, -1이 존재하므로 바로 '+' 연산자를 사용하면 됩니다.

다만 이를 하나의 정점마다 '4번' 반복해야 하므로, 이를 for로 4번 반복하도록 묶어주어야 합니다.

for (int i = 0; i < 4; i++) {
    int nextY = cur.y + dy[i];
    int nextX = cur.x + dx[i];
    if (nextY < 0 || nextX < 0 || startY >= n || startX >= m)
        continue;  // out of bound
    if (Map[nextY][nextX] == 1 && visited[nextY][nextX] == false) {
        q.push({nextY, nextX, cur.turn + 1});
        visited[nextY][nextX] = true;
    }
}

다음 행과 열의 인덱스를 구했다면, 최우선적으로 할일은 "가능한" 인덱스 범위안인지를 판단하는 일입니다.

이는 문제마다 다르지만, 대개 입력으로 받은 Map의 범위와 같은, [0, n-1]과 [0, m-1]입니다.

nextY나 nextX의 값은 0은 물론이고 일시적으로 -1까지도 들어갈 수 있는데

이후에 입력받은 2차원 배열인 Map[][]과 방문처리를 위한 visited[][]의 인덱스로 들어가므로

4-5라인의 예외처리가 없다면 런타임에러가 발생합니다. Map[-1][0]같은곳을 참조하려고 했기 때문입니다.

 

nextY와 nextX가 가능한 인덱스 범위라면, 이 문제에서는 2가지를 더 판별해야 합니다.

각각 "지나갈 수 있는 정점인가?"와 "아직 방문하지 않은 정점인가?"입니다.

전자의 경우 문제마다 장애물이 존재한다면, 그에 대한 구현은 if()의 조건을 달아서 해결하는 셈입니다.

 

후자의 경우, 일반적으로 BFS는 재방문을 허용하지 않습니다.

재방문을 허용해야하는 문제는 대체로 아래와 같습니다.

그 외에는 항상 재방문을 허용하지 않는것으로 간주해도 무방합니다.

-> 재방문을 허용해야하는 경우 : (1,1)에서 (N,M)까지 가는 최단경로의 개수는?

 

 

여기까지 기본적인 bfs의 구현방법과 그 의미를 최대한 간략하게 소개했습니다.

소스코드 역시 읽는데에 어려움이 없으면서 어느정도의 확장성을 갖추기를 바라며 작성했습니다만,

실제로 BOJ에서 bfs문제를 해결하기 위해서는 어떠한 코드이든 완전히 재활용을 할 수 있지는 않을겁니다.

 

아마 처음 bfs를 배우시는 분이라면,  알고리즘과 자료구조가 묘하게 혼합된 형태가

익숙하지 않고 어렵다고 생각하실 수 있을것 같습니다.

위 코드는 미로탐색(https://www.acmicpc.net/problem/2178)문제를 해결한 소스코드이며

미로탐색 문제를 bfs로 해결한 다른 소스코드도 많이 읽어보시길 권장하며, 때론 따라쳐보기도 하길 추천드립니다.

어느순간 어렵게만 느껴졋던 난이도의 문제가, 결국 비슷비슷한 웰노운으로 느껴지는 순간을 겪으시길 바랍니다.

 

 

아래는 위 미로 탐색 문제 같은 기본적인 bfs를 바탕으로  bfs가 어떠한 형태로 출제되는지를 유형화했습니다.

 

<1> 플러드필

 

1-1 영역의 넓이 구하기 : [2667] 단지번호붙이기, [7569] 토마토, [4963] 섬의 개수

일반적으로 2차원 배열이 입력되고, 문제에서 "연결"과 "분리"를 정의합니다.

이를 바탕으로 "연결된 공간"에 대한 탐색을 진행하는 형태이며, 영역의 넓이를 묻는 문제는

bfs라고 알아보기 쉽다는 특징이 있습니다. 

"단지번호붙이기"는 2차원 배열에서의 영역의 넓이를 구하는 문제이고,

"토마토"는 2차원 배열이 아닌 3차원 배열입니다.

"섬의 개수"는 "단지번호붙이기"에서 보았던 4방향과 달리, 대각선으로도 연결된 8방향입니다.

 

"[2667] 단지번호붙이기" 해설 : https://dizlet.tistory.com/151

"[7569] 토마토" 해설 : https://dizlet.tistory.com/152

"[4963] 섬의 개수" 해설 : https://dizlet.tistory.com/153

 

1-2 영역의 넓이 구하기(심화) : [16946] 벽 부수고 이동하기 4

의외로 난이도가 높은문제, 시간초과에 유의해야 합니다.

 

"[16946] 벽 부수고 이동하기 4" 해설 : https://dizlet.tistory.com/150 

 

1-3 BFS + 시뮬레이션 : [2573] 빙산, [2638] 치즈

"빙산"과 "치즈"모두, 인접한 부분에 특별한 연산을 해주어야 합니다.

"빙산은 바다에 닿은 만큼 녹는다", "공기와 닿아있는 치즈는 녹는다"는 부분을 구현해야 하며,

인접한 부분을 파악하기 위해서 BFS를 사용하곤 합니다.

'빙산"의 경우 빙산의 분리를 판별하는 부분

"치즈"의 경우 "치즈 내부의 공간"에 대한 처리가 어렵습니다.

 

"[2573]빙산" 해설 : https://dizlet.tistory.com/145

"[2638]치즈" 해설 : https://dizlet.tistory.com/146

 

<2> 최단경로, 최적해구하기

BFS의 핵심 특성중 하나인, "먼저 도착하는것이 최적해"라는 특성을 살려서 해결하는 유형입니다.

 

2-1 최단경로 구하기 : [2178] 미로탐색, [7562] 나이트의 이동

역시 2차원 배열이 입력됩니다. "시작점"과 "도착점"이 주어지고

"시작점"에서 "도착점"까지 도달하기 위한 비용 내지 거리를 출력해야합니다.

해당 위치를 지날 수 없는, "장애물"이 존재하기도 합니다.

"미로탐색"의 경우, 2차원 배열 입력 + 4방향이라는, 정석적인 문제이며

"나이트의 이동"은 방향데이터의 변형으로 구현할 수 있습니다.

 

상당히 다양한 형태로 등장하며, 어려운 문제의 경우

그리디를 bfs로 착각하거나 메모이제이션 dfs를 bfs로 착각하기도 쉽습니다. 이경우 시간초과가 나옵니다.

 

"[2178] 미로탐색" 해설 : https://dizlet.tistory.com/154

"[7562] 나이트의 이동" 해설 : https://dizlet.tistory.com/155

 

2-2 최단경로 구하기(심화) : [1600]말이 되고픈 원숭이, [12851] 숨바꼭질 2

"말이 되고픈 원숭이"는 방향데이터의 추가, 하나의 정점을 이루는 요소를 변화해야 해결할 수 있습니다.

"숨바꼭질"시리즈는 입력이 다른 문제들과 다르지만, bfs로 접근할 수 있습니다.

그중 "숨바꼭질2"의 경우, 아무 생각 없이 queue에 push하자마자 visited를 true로 변경하면 틀립니다.

 

"[1600]말이 되고픈 원숭이" 해설 : https://dizlet.tistory.com/53

"[12851]숨바꼭질 2" 해설 : https://dizlet.tistory.com/121

 

2-3 최단경로 + 역추적 : [13913] 숨바꼭질 4

2차원 배열에서의 역추적과, 숨바꼭질같이 단순한 숫자에서의 역추적의 원리는 같습니다.

"시작점"에서 출발하여 "도착점"에 도달하고, 이것이 정답이라고 확신할 수 있다면

"도착점"에서 출발하여, "시작점"까지 다시 돌아오는 방식입니다.

 

"[13913]숨바꼭질 4" 해설 : https://dizlet.tistory.com/33

 

2-4 0-1 BFS : [13549]숨바꼭질 3, [1261] 알고스팟, [9376] 탈옥

BFS의 전제조건중 하나는, "모든 가중치가 동일할것"입니다.

물론, 가중치가 3으로 동일하든, 1로 동일하든 아무 상관은 없습니다.

하지만, 위 3문제는 가중치과 0혹은 1입니다.

가중치중 음수인것이 없으므로 다익스트라를 사용하여 해결할 수 있지만, 가중치가 0혹은 1이라면

꽤 특별한 형태의 BFS테크닉을 적용하여 다익스트라보다 빠르게 문제를 해결할 수 있습니다. 

구현은 생각보다 단순한데, 아래의 과정으로 BFS코드를 0-1 BFS코드로 바꿉니다.

1. queue를 deque로 바꾼다.

2. pop은 항상 pop_front에서 진행한다.

3. 가중치가 0이면 front()에, 1이면 back()에 push한다.

 

"숨바꼭질 3"과 "알고스팟"은 다양한 풀이가 존재하며, 0-1 BFS를 사용해야만 풀리는것은 아닙니다.

"탈옥"의 경우, 종료조건의 구체화가 어렵지만, 역시 다익스트라나 0-1 BFS로 해결합니다.

 

"[13549]숨바꼭질 3" 해설 : https://dizlet.tistory.com/120 

"[1261] 알고스팟" 해설 : https://dizlet.tistory.com/104

"[9376]탈옥" 해설 : https://dizlet.tistory.com/139