[C++/코테] BFS

개념 설명 글이므로 언어와 상관없이 읽으실 수 있습니다. 

혹시 파이썬 기반 개념 설명이 궁금하시다면 아래 포스팅을 참고해주세요 :)

2023.04.21 - [Algorithm] - [Python/코테] DFS/BFS (1) - 개념, 스택, 재귀함수

[Python/코테] DFS/BFS (1) - 개념, 스택, 재귀함수

---

Intro.

윤곽선 내부만을 칠해주는 기능을 Flood Fill 이라고 한다. 이 기능은 오늘 포스팅에서 다룰 BFS로 구현 가능하다.

source: https://lodev.org/cgtutor/floodfill.html

BFS

• Breadth First Search
• 다차원 배열에서 각 칸을 방문할 때 너비를 우선으로 방문하는 알고리즘. 
• 그래프 자료구조(정점과 간선으로 이루어진 구조)에서 모든 노드를 방문하기 위한 알고리즘.

좌표를 담을 큐와 방문 여부를 표시할 배열이 필요하다. 방문하면 큐에 push하고, 재방문 시 pop한다.

여기서 재방문의 경우는 아예 방문하지 않은 곳으로의 이동을 위해 오게 되는 경우이다. 1회 이상의 방문 여부는 큐가 아닌 배열의 값으로 확인해야 한다.

큐가 비워지면 시작점에서의 탐색 과정이 끝났다고 본다. (* 만약 공간을 여러 번 확인(=bfs 여러 번 진행)해야 한다면, 큐를 채웠다 완전히 비워지는 것을 기준으로 생각하면 이해가 편하다.)

 

이를 번호 매기면 다음과 같다.

1. 시작하는 칸을 큐에 넣고 방문했다는 표시를 남김.
2. 큐에서 원소를 꺼내어 그 칸에 상하좌우로 인접한 칸에 대해 3번을 진행
3. 해당 칸을 이전에 방문했다면 아무 것도 하지 않고, 처음 방문했다면 방문 표시를 남기고 해당 칸을 큐에 삽입
4. 큐가 비워질 때까지 2번을 반복한다.

모든 칸이 큐에 1번씩 들어가므로 시간 복잡도는 칸이 N개일 때, $O(N)$이다.

구현

STL 라이브러리의 utility 헤더의 pair를 사용한다. make_pair 혹은 중괄호를 사용하여 두 자료형을 묶을 수 있다.

#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second			// pair에서 first, second를 줄여서 쓰기 위해서 사용

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({0, 0});				// 큐에 시작점인 (0, 0)을 삽입.
    
    // 큐가 비워질 때까지 상하좌우 칸 방문
    while (!Q.empty())
    {
        pair<int, int> cur = Q.front();
        Q.pop();
        cout << '(' << cur.X << ", " << cur.Y << ") -> ";	// 방문 순서를 나타내기 위한 출력문
        
        // 상하좌우 칸을 살펴보는 코드 (x: 행(가로), y: 열(세로)-주의!)
        for (int dir = 0; dir < 4; dir++)
        {
            int nx = cur.X + dx[dir];
            int ny = cur.Y + 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({nx, ny});
        }
    }
}

 

main 함수의 for 반복문에서 x가 행, y가 열이라는 것은 아래와 같은 의미가 된다. 일반적이 좌표와 조금 다른 형태.

대부분의 BFS에서 이렇게 사용하기 때문에 유념해두자.

 

백준 1926번 그림 문제를 통해 기본적인 BFS 문제를 풀어보자.

Flood Fill 응용 문제이다.

2023.11.11 - [Algorithm] - [Python/코테] 백준 1926 그림

[Python/코테] 백준 1926 그림

예제 및 응용

응용1. 거리 측정

• 백준 2178번 미로 탐색
• https://www.acmicpc.net/problem/2178
• 다차원 배열에서의 거리 측정

응용2. 시작점이 여러 개일 때

• 백준 7576번 토마토 
• https://www.acmicpc.net/problem/7576
• 시작점이 여러 개인 BFS 함수 반복 필요 → 모든 시작점을 큐에 넣고, BFS를 실행한다.
• 거의 비슷한 유형이지만 3차원 배열을 사용하는 문제는 백준 7569번에 있다.

응용3. 시작점이 두 종류일 때

• 백준 4179번 불!
• https://www.acmicpc.net/problem/4179
• 서로의 영향 관계를 파악하여 두 번의 BFS를 실행한다. 이 문제에서는 두 번째 BFS(지훈이의 이동)를 실행할 때, 앞의 BFS(불의 이동)로 생긴 추가 조건이 생기는 것

응용4. 1차원에서의 BFS

• 백준 1697번 숨바꼭질
• https://www.acmicpc.net/problem/1697
• 2차원에서 상하좌우로의 이동이 아니라, 앞뒤의 이동으로 바꾼다.
• BFS의 범위를 논리적으로 생각하여 정해준다.