백준 1012 - 유기농 배추 [C++]

https://www.acmicpc.net/problem/1012

1012번: 유기농 배추

---

풀이 과정

상하좌우 배추에 배추흰지렁이가 옮겨서 해충으로 부터 보호할 수 있을 때, 격자 모양의 밭의 모든 배추를 보호하려면 배추흰지렁이가 몇 마리 필요한지 구하는 문제이다.

 

연결 요소의 개수를 구하라는 문제와 같다. flood-fill을 bfs로 구현하고 미방문 배추를 bfs로 방문해주면서 연결 요소의 개수를 세주면 된다.

---

소스 코드

#include <iostream>
#include <queue>
using namespace std;
bool board[51][51];
bool visit[51][51];
int dy[4] = {0, 1, 0, -1};
int dx[4] = {1, 0, -1, 0};
int M, N, K;

void bfs(int y, int x) {
    queue<pair<int, int>> Q;
    visit[y][x] = true;
    Q.push(make_pair(y, x));

    while(!Q.empty()) {
        auto cur = Q.front(); Q.pop();
        for (int i = 0; i < 4; i++) {
            int ny = cur.first + dy[i];
            int nx = cur.second + dx[i];

            if (0 <= ny && ny < N && 0 <= nx && nx < M) {
                if (!board[ny][nx]) continue;
                if (visit[ny][nx]) continue;
                visit[ny][nx] = true;
                Q.push(make_pair(ny, nx));
            }
        }
    }
}

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

    int T;
    cin >> T;
    while(T--) {
        cin >> M >> N >> K;
        int Y, X;
        int answer = 0;

        for (int i = 0; i < K; i++) {
            cin >> X >> Y;
            board[Y][X] = true;
        }

        for (int i = 0 ; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (board[i][j] && !visit[i][j]) {
                    answer++;
                    bfs(i, j);
                }
            }
        }

        cout << answer << '\n';


        for (int i = 0; i < 51; i++) {
            for (int j = 0; j < 51; j++) {
                board[i][j] = false;
                visit[i][j] = false;
            }
        }
    }

    return 0;
}