1. 알고리즘 설명

• BFS : 다차원 배열에서 각 칸을 방문할 때 너비를 우선으로 방문하는 알고리즘
  • 그래프 탐색을 위한 알고리즘
  • 큐 사용해 구현
• Cf) DFS : 깊이 우선 방문, 스택 사용해 구현

2. 예시

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

참고 : STL Pair

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

int main(void) {
  pair<int, int> t1 = make_pair(10, 13);
  pair<int, int> t2 = {4, 6};
  
  cout << t2.first << ' ' << t2.second << '\n';
  if (t2 < t1) cout << "t2 < t1";
}

• pair에서의 비교: 앞쪽의 값 우선 비교 후 뒤쪽의 값 비교

구현 시 자주 틀리는 부분

1. 시작점에 방문했다는 표시를 남기지 않는다.
2. 큐에 넣을 때 방문했다는 표시를 하는 대신, 큐에서 빼낼 때 방문 표시를 한다.
3. 이웃한 원소가 범위를 벗어났는지에 대한 체크를 잘못했다.

3. 응용

1. 기본

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

#define X first
#define Y second

int paper[505][505];
bool visited[505][505];
int n, m;

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

int dfs(pair<int, int> start) {
    queue<pair<int, int>> q;
    q.push(start);
    visited[start.X][start.Y] = 1;
    int area = 0;
    while (!q.empty()) {
        pair<int, int> cur = q.front(); q.pop();
        area++;
        for (int dir = 0; dir < 4; dir++) {
            int nx = cur.X + dx[dir];
            int ny = cur.Y + dy[dir];
            if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
            if (visited[nx][ny] || !paper[nx][ny]) continue;
            visited[nx][ny] = 1;
            q.push({nx, ny});
        }
    }

    return area;
}

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

    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> paper[i][j];
        }
    }
    int paintNum = 0;

    int max = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (paper[i][j] && !visited[i][j]) {
                paintNum++;
                int area = dfs({i, j});
                if (max < area) max = area;
            }
        }
    }

    cout << paintNum << '\n';
    cout << max << '\n';
}

2. 거리 측정

https://boj.kr/2178

dist 배열 -1 초기화

시작 점으로부터의 이동 거리 저장

3. 시작점이 여러 개일 때

https://boj.kr/7576

모든 시작점을 큐에 넣고 DFS 돌리기

• STL 튜플 → 삼차원 토마토 참고
• BFS를 돌 때 큐에 쌓이는 원소는 반드시 거리 순

4. 시작점이 두 종류일 때

https://boj.kr/4179

불에 대한 bfs + 지훈이에 대한 bfs

(두 요소가 서로 영향을 주고받으면 백트래킹 기법을 추가로 사용해야 함 → 시간순으로 A, B 동시 진행)

5. 벽 부수고 이동하기

https://boj.kr/2206

벽을 부수지 않은 경우의 distance 배열 + 벽을 부순 경우의 distance 배열

BFS의 특성 상 각 상태에 대해 최초 도달한 경로가 최단 경로이므로, 굳이 어떤 벽을 부수었는지 따로 저장하거나 여러 벽 부수기 경우를 관리할 필요는 없음에 유의

출처 및 참고자료 : 바킹독의 실전 알고리즘