BFS

06 Dec 2023 in Posts on Algo, CPP

“0x09강 - BFS”

• BFS(Breadth-first Search)
  • 워크북
  • BFS 문제를 풀어보기 전에
    • 가로세로연구소
    • bfs 연습 코드
  • BOJ 1926 (그림)
  • BOJ 2178 (미로 탐색)
  • BOJ 4179 (불!)
  • BOJ 1697 (숨바꼭질)
  • BOJ 7569 (토마토)
    • input과 direction 배열
    • board 채우기
    • bfs 돌리기
  • BOJ 6593 (상범 빌딩)

BFS(Breadth-first Search)

[바킹독 실전 알고리즘] 0x09강 - BFS

워크북

분류	백준 번호	문제 제목
연습 문제	1926	그림
연습 문제	2178	미로 탐색
연습 문제	7576	토마토
연습 문제	1697	숨바꼭질
기본 문제✔	1012	유기농 배추
기본 문제✔	10026	적록색약
기본 문제✔	7569	토마토
기본 문제✔	5427	불
기본 문제✔	2583	영역 구하기
기본 문제✔	2667	단지번호붙이기
기본 문제✔	5014	스타트링크
기본 문제✔	2468	안전 영역
기본 문제✔	6593	상범 빌딩

• bfs, dfs, 백트래킹같은 주요 유형같은 경우 기본적으로 양치기를 한다. 배웠던 점에 대해 다뤄본다.

BFS 문제를 풀어보기 전에

가로세로연구소

세로 → 행, 가로 → 열

            0번째 열   1번째 열 → 가로 (M)
0번째 행  ->     ↓         ↓
1번째 행  ->
2번째 행  ->
 ↓ 세로 (N)

• 입력으로 주어지는 N, M, 세로, 가로, R, C, 행, 열에 대한 개념을 제대로 잡아놓지 않으면 풀때마다 고통을 겪게 된다. 물론 거의 대부분의 문제가 정해진 루틴에 따라 입력을 쥐어주지만, 가끔 N, M을 뒤바꿔서 입력을 주는 악질적인 문제도 있다.

• 보통 입력은 N이 먼저, 그 다음으로 M이 주어진다. N이 세로 길이로 주어지고, M이 가로 길이로 주어진다. 세로 길이는 행의 길이를 의미하고, 가로 길이는 열의 길이를 의미한다.

• 예를 들어 N과 M이 3과 5로 주어졌다면? N은 세로 길이(행), M이 가로 길이(열)이니까…

1	1	0	1	1
1	0	1	0	1
1	0	1	0	1

• 이런 식으로 그림을 그릴 수 있겠다. 1과 0은 input에 따라 다르게 배치될 수 있을 것이다.

bfs 연습 코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <deque>
#include <map>
#include <list>
#include <utility>
#define all(x) (x).begin(), (x).end()
#define rep(i, a, b) for (int i = (a); i < (b); ++i)
using namespace std;

int board[502][502] =
    {1,1,1,0,1,0,0,0,0,0},
    {1,0,0,0,1,0,0,0,0,0},
    {1,1,1,0,1,0,0,0,0,0},
    {1,1,0,0,1,0,0,0,0,0},
    {0,1,0,0,0,0,0,0,0,0},
    {0,0,0,0,0,0,0,0,0,0},
    {0,0,0,0,0,0,0,0,0,0}; // 1이 파란 칸, 0이 빨간 칸에 대응

bool vis[502][502]; // 해당 칸을 방문했는지 여부를 저장

int n = 7, m = 10; // n = 행의 수, m = 열의 수
int dx[4] = {1, 0, -1, 0}; //                      ↙↖
int dy[4] = {0, 1, 0, -1}; // 상하좌우 네 방향을 의미   ↘↗ 하, 우, 상, 좌

int main(void)
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    queue<pair<int,int> > Q;
    vis[0][0] = 1; // (0, 0)을 방문했다고 명시
    Q.push(make_pair(0, 0)); // 큐에 시작점인 (0, 0)을 삽입.

    while(!Q.empty())
    {
        pair<int,int> cur = Q.front(); 
        Q.pop();
        cout << '(' << cur.first << ", " << cur.second << ") -> ";
        for (int dir = 0; dir < 4; dir++)
        {   // 상하좌우 칸을 살펴볼 것이다.
            int nx = cur.first + dx[dir];
            int ny = cur.second + dy[dir]; 
            // nx, ny에 dir에서 정한 방향의 인접한 칸의 좌표가 들어감
            if (nx < 0 || nx >= n || ny < 0 || ny >= m) 
                continue; // 범위 밖일 경우 넘어감
            if (vis[nx][ny] || board[nx][ny] != 1) 
                continue; // 이미 방문한 칸이거나 파란 칸이 아닐 경우
            vis[nx][ny] = 1; // (nx, ny)를 방문했다고 명시
            Q.push(make_pair(nx, ny));
        }
    }
}

• 천자문 외우듯이 줄줄 외우면 된다 그냥. 누가 쓰라고 하면 자다가도 쓸 수 있어야 한다. 모든 Bfs 문제는 이거보고 풀 수 있다.

BOJ 1926 (그림)

#include <bits/stdc++.h>
using namespace std;

int board[505][505];
int vis[505][505];
int n, m, mx, num; // 6 5
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    cin>>n; cin>>m;

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

    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            if (board[i][j] == 0 || vis[i][j])
                continue;
            num++;
            queue< pair<int, int> > q;
            vis[i][j] = 1;
            q.push(make_pair(i, j));
            int area = 0;
            while (!q.empty())
            {
                area++;
                pair<int, int> cur = q.front();
                q.pop();
                for (int dir = 0; dir < 4; dir++)
                {
                    int nx = cur.first + dx[dir];
                    int ny = cur.second + dy[dir];
                    if (nx < 0 || nx >= n || ny < 0 || ny >= m)
                        continue;
                    if (vis[nx][ny] || board[nx][ny] != 1)
                        continue;
                    vis[nx][ny] = 1;
                    q.push(make_pair(nx, ny));
                }
            }
            mx = max(mx, area);
        }
    }
    cout << num << '\n' << mx;    
    return 0;
}

• 2차원 board의 모든 원소에 대해 Bfs를 진행하기 위해 이중 for 문을 돈다.

• bfs를 실행하는 것이 구역의 개수이고(num)이고, 각 구역의 넓이가 area인데, 아직 area의 위치가 헷갈린다. vis[nx][ny]를 할때 area를 1씩 늘려도 되는게 아닌가 싶은데, 그렇게 하면 틀리게 된다. while문의 첫부분에서 area를 더해준다.

BOJ 2178 (미로 탐색)

#include <bits/stdc++.h>
using namespace std;

int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
int board[101][101];
int dist[101][101];
int n, m;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    cin >> n >> m;

    for (int i = 0; i < n; i++)
    {
        string s;
        cin >> s;
        for (int j = 0; j < m; j++)
            board[i][j] = s[j] - '0';
    }

    for (int i = 0; i < n; i++)
        fill(dist[i], dist[i] + m, -1);

    queue< pair<int, int> > q;
    dist[0][0] = 0;
    q.push(make_pair(0, 0));

    while(!q.empty())
    {
        pair<int, int> cur = q.front(); q.pop();
        for (int dir = 0; dir < 4; dir++)
        {
            int nx = cur.first + dx[dir];
            int ny = cur.second + dy[dir];
            if (nx < 0 || nx >= n || ny < 0 || ny >= m)
                continue;
            if (dist[nx][ny] >= 0 || board[nx][ny] != 1)
                continue;
            dist[nx][ny] = dist[cur.first][cur.second] + 1;
            q.push(make_pair(nx, ny));
        }
    }
    cout << dist[n - 1][m - 1] + 1;
    return 0;
}

• vis[][] 배열 대신 dist[][] 배열이 들어온다. 단순히 방문 여부만 알 수 있었던 vis 배열에서 진일보하여 몇번의 이동에 해당 칸까지 갈 수 있는지 알 수 있게 된다. 조건을 체크하면서 목적지의 dist값을 출력하면 된다.

if (nx < 0 || nx >= n || ny < 0 || ny >= m)
    continue;
if (dist[nx][ny] >= 0 || board[nx][ny] != 1)
    continue;
dist[nx][ny] = dist[cur.first][cur.second] + 1;

• 조건을 체크하면서 이전 dist 값에서 하나씩 더해간다.

BOJ 4179 (불!)

#include <bits/stdc++.h>
using namespace std;

int n, m;
string board[1010];
int mov[1010][1010];
int fire[1010][1010];
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    cin >> n; cin >> m;

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

    for (int i = 0; i < n; i++)
    {
        fill(fire[i], fire[i] + m, -1);
        fill(mov[i], mov[i] + m, -1);
    }

    queue< pair<int, int> > q1; // fire
    queue< pair<int, int> > q2; // mov

    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            if (board[i][j] == 'F') {
                q1.push(make_pair(i, j));
                fire[i][j] = 0;
            }
            if (board[i][j] == 'J') {
                q2.push(make_pair(i, j));
                mov[i][j] = 0;
            }
        }
    }

    while (!q1.empty()) // 불의 dfs
    {
        pair<int, int> cur = q1.front(); q1.pop();
        for (int dir = 0; dir < 4; dir++)
        {
            int nx = cur.first + dx[dir];
            int ny = cur.second + dy[dir];
            if (nx < 0 || nx >= n || ny < 0 || ny >= m)
                continue;
            if (fire[nx][ny] >= 0 || board[nx][ny] == '#')
                continue;
            fire[nx][ny] = fire[cur.first][cur.second] + 1;
            q1.push(make_pair(nx, ny));
        }
    }

    while (!q2.empty()) // j의 dfs
    {
        pair<int, int> cur = q2.front(); q2.pop();
        for (int dir = 0; dir < 4; dir++)
        {
            int nx = cur.first + dx[dir];
            int ny = cur.second + dy[dir];
            if (nx < 0 || nx >= n || ny < 0 || ny >= m) {
                cout << mov[cur.first][cur.second] + 1;
                return 0; 
            }
            if (mov[nx][ny] >= 0 || board[nx][ny] == '#')
                continue;
            if (fire[nx][ny] != -1 && fire[nx][ny] <= mov[cur.first][cur.second] + 1)
                continue;
            mov[nx][ny] = mov[cur.first][cur.second] + 1;
            q2.push(make_pair(nx, ny));
        }
    }
    cout << "IMPOSSIBLE";
    return 0;
}

• 지훈이가 불이 번지기 전에 탈출할 수 있는지의 여부를 판단해야 한다. 불이 번지는 것과 지훈이 움직이는 경로에 대해 모두 bfs를 실행해야 한다. 다만 불이 번지는 것과 지훈이가 움직이는 상황은 별개의 상황으로 서로가 영향을 미치지 않기 때문에 불을 먼저 전파시켜서 불의 전파 속도를 구한 이후, 지훈이를 움직이면서 조건에 불의 전파 속도를 추가하여 지훈이가 불보다 빠른 타일에서만 움직이도록 하면 된다. (불의 배열 fire[][]와 지훈이의 움직임 배열 mov[][]를 따로 만들어서 씀)

• 이렇게 두 상황에 대해 bfs를 하는 경우에 만약 두 상황이 서로에게 영향을 준다면 이런 식으로 따로 bfs를 하면 안된다고 한다.

BOJ 1697 (숨바꼭질)

#include <bits/stdc++.h>
using namespace std;

int N, K;
int dist[202020];

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    cin >> N; cin >> K;
    queue<int>  q;

    fill(dist, dist + 202020, -1);

    dist[N] = 0;
    q.push(N);

    while (!q.empty())
    {
        int cur = q.front(); q.pop();
        if (cur == K)
            break ;
        for (int dir = 0; dir < 3; dir++)
        {
            int newcur;
            if (dir == 0)
                newcur = cur + 1;
            else if (dir == 1)
                newcur = cur - 1;
            else
                newcur = cur * 2;
            if (newcur < 0 || newcur > 202020 || dist[newcur] >= 0)
                continue ;
            dist[newcur] = dist[cur] + 1;
            q.push(newcur);
        }
    }
    cout << dist[K];
    return 0;
}

• 항상 2차원 board에 대해서만 bfs를 돌려왔던 여태가지의 문제들과 달리, 1차원 배열에서 bfs를 돌리게 된다.

• 대략 위 그림처럼 bfs를 진행하면서 거리표를 채운다. 1차원 배열이기 때문에 board도 필요없고, dist 일차원 배열만 사용하면 된다. dir 배열 dx[4], dy[4]도 필요 없다. 문제에서 주어진 이동 경로 +1, -1, *2에 대한 for문만 돌리면 된다. 물론 bfs를 돌리는 틀은 바뀐게 전혀 없다. 조건문도 거의 똑같다. 다만 배열의 인덱스를 초과하는 것을 방지하기 위해, 인덱스 초과에 대한 예외를 먼저 체크한 이후 dist[]의 방문 여부를 체크해야 한다. 순서가 잘못되면 outofBound 세그멘테이션 폴트가 발생한다.

BOJ 7569 (토마토)

#include <bits/stdc++.h>
using namespace std;

int M, N, H; // M 가로길이, N 세로길이, H 상자높이
int dx[6] = {0, 0, 1, -1, 0, 0};
int dy[6] = {1, -1, 0, 0, 0, 0};
int dz[6] = {0, 0, 0, 0, 1, -1};
int board[103][103][103];
int dist[103][103][103];
queue<pair<int, pair<int, int> > > q;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    cin >> M >> N >> H;

    for (int i = 0; i < H; i++)
    {
        for (int j = 0; j < N; j++)
        {
            for (int k = 0; k < M; k++)
            {
                int tmp;
                cin >> tmp;
                board[j][k][i] = tmp;
                if (tmp == 1) q.push(make_pair(j, make_pair(k, i)));
                if (tmp == 0) dist[j][k][i] = -1;
            }
        }
    }

    while (!q.empty())
    {
        pair<int, pair<int, int> > cur = q.front(); q.pop();
        int curX, curY, curZ;
        curX = cur.first;
        curY = cur.second.first;
        curZ = cur.second.second;
        for (int dir = 0; dir < 6; dir++)
        {
            int nx = curX + dx[dir];
            int ny = curY + dy[dir];
            int nz = curZ + dz[dir];
            if (nx < 0 || nx >= N || ny < 0 || ny >= M || nz < 0 || nz >= H) 
                continue;
            if (dist[nx][ny][nz] >= 0) continue;
            dist[nx][ny][nz] = dist[curX][curY][curZ] + 1;
            q.push(make_pair(nx, make_pair(ny, nz)));
        }
    }

    int ans = 0;
    for (int i = 0; i < H; i++)
    {
        for (int j = 0; j < N; j++)
        {
            for (int k = 0; k < M; k++)
            {
                if (dist[j][k][i] == -1) {
                    cout << -1 << '\n';
                    return 0;
                }
                ans = max(ans, dist[j][k][i]);
            }
        }
    }
    cout << ans << '\n';
    return 0;
}

• 1, 2차원 bfs에 이어 3차원 bfs이다. 토마토 상자의 세로, 가로, 높이가 주어지고 토마토가 모두 익는 시점을 구하게 된다. 솔직히 스스로 풀어낼 자신이 없어서 정답 코드를 참조했다. 기존의 2차원 bfs에서 확장되는 부분에 대해서 공부해두는 것이 좋겠다.

input과 direction 배열

int board[103][103][103];
int M, N, H; // M 가로길이, N 세로길이, H 상자높이
int dx[6] = {0, 0, 1, -1, 0, 0};
int dy[6] = {1, -1, 0, 0, 0, 0};
int dz[6] = {0, 0, 0, 0, 1, -1};

• 2차원 보드는 아래 -> 오른쪽 -> 위 -> 왼쪽으로 가는 dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1} 배열이 있는데 3차원 보드는 무슨 방향으로 움직이는 건지 머릿속에 그려지지가 않는다. 일단 위처럼 사용한다.

board 채우기

for (int i = 0; i < H; i++)
{
    for (int j = 0; j < N; j++)
    {
        for (int k = 0; k < M; k++)
        {
            int tmp; cin >> tmp;
            board[j][k][i] = tmp; // 세로, 가로, 높이 순서로 채움
            if (tmp == 1) 
                q.push(make_pair(j, make_pair(k, i)));
            if (tmp == 0) 
                dist[j][k][i] = -1;
        }
    }
}

• board를 채우는데, 처음에는 왜 N, M, H (board[j][k][i], 세로->가로->높이) 순서대로 보드를 채우는건지 알 수 없었다. 내 눈에는 높이->세로->가로(board[i][j][k], N, M, H) 순서대로 채우는게 자연스러워 보였기 때문이다. 근데 사실 여기서 어느 순서대로 채우는지는 별 상관없다. 다만 여기서 채운 순서와 나중에 dist 배열을 채우는 순서가 어긋나서는 안된다. 여기서 세로 가로 높이 순서로 채웠으면 나중에 dist를 채울때도 세로 가로 높이 순서대로 채워야 한다.

bfs 돌리기

while (!q.empty())
{
    pair<int, pair<int, int> > cur = q.front(); q.pop();
    int curX, curY, curZ;
    curX = cur.first;
    curY = cur.second.first;
    curZ = cur.second.second;
    for (int dir = 0; dir < 6; dir++)
    {
        int nx = curX + dx[dir];
        int ny = curY + dy[dir];
        int nz = curZ + dz[dir];
        if (nx < 0 || nx >= N || ny < 0 || ny >= M || nz < 0 || nz >= H) 
            continue;
        if (dist[nx][ny][nz] >= 0) continue;
        dist[nx][ny][nz] = dist[curX][curY][curZ] + 1;
        q.push(make_pair(nx, make_pair(ny, nz)));
    }
}

• cph에서 c++11 컴파일러를 쓸수가 없어서 tuple을 못써서, pair안에 pair를 넣어서 못생긴 코드를 쓸 수 밖에 없다. 위에서 board를 세로 가로 높이로 채웠기 때문에 dist도 dist[nx][ny][nz]와 같이 세로 가로 높이로 받는다. 만약 위에서 높이 세로 가로로 받았다면 dist를 dist[nz][nx][ny]로 받아야 했을 것이다. 그 외에는 기존 bfs와 거의 다른 점이 없다.

BOJ 6593 (상범 빌딩)

#include <bits/stdc++.h>
using namespace std;

int L, R, C;
int dx[6] = {0, 0, 1, -1, 0, 0};
int dy[6] = {1, -1, 0, 0, 0, 0};
int dz[6] = {0, 0, 0, 0, 1, -1};

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    while (1)
    {
        cin >> L >> R >> C;

        if (L == 0 && R == 0 && C == 0)
            break;

        queue<pair<int, pair<int, int> > > q;
        char board[33][33][33];
        int dist[33][33][33];
        
        for (int j = 0; j < R; j++)
            for (int k = 0; k < C; k++)
                fill(dist[j][k], dist[j][k] + L, 0);

        for (int i = 0; i < L; i++)
        {
            for (int j = 0; j < R; j++)
            {
                for (int k = 0; k < C; k++)
                {
                    cin >> board[j][k][i];
                    if (board[j][k][i] == 'S') {
                        q.push(make_pair(j, make_pair(k, i)));
                        dist[j][k][i] = 0;
                    }
                }
            }
        }

        bool isEscape = false;
        while (!q.empty())
        {
            if (isEscape)
                break;
            pair<int, pair<int, int> > cur = q.front(); q.pop();
            int curX, curY, curZ;
            curX = cur.first;
            curY = cur.second.first;
            curZ = cur.second.second;
            for (int dir = 0; dir < 6; dir++)
            {
                int nx = curX + dx[dir];
                int ny = curY + dy[dir];
                int nz = curZ + dz[dir];
                if (nx < 0 || nx >= R || ny < 0 || ny >= C || nz < 0 || nz >= L) 
                    continue;
                if (board[nx][ny][nz] == '#' ||
                dist[nx][ny][nz] > 0)
                    continue;
                dist[nx][ny][nz] = dist[curX][curY][curZ] + 1;
                if (board[nx][ny][nz] == 'E')
                {
                    cout << "Escaped in " << dist[nx][ny][nz] << " minute(s).\n";
                    isEscape = true;
                    break;
                }
                q.push(make_pair(nx, make_pair(ny, nz)));
            }  
        }
        if (!isEscape)
            cout << "Trapped!\n";
    }
    return 0;
}

• 바로 위의 토마토와 거의 유사한 문제, 다만 보드를 받을 때 높이 세로 가로 순서로 받아서 dist를 채울때에도 dist[nx][ny][nz]의 순서로 채운 것이 차이점.