(백준/C++) 1012-유기농 배추

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

문제 해석(시간 제한 1초)

배추를 해충으로 보호하기 위해서는 배추흰지렁이를 필요로 하다고 합니다. 배추 뭉치 한 곳당 지렁이 한마리가 필요하다고 합니다. 이 지렁이가 필요한 개수를 구하는 것이 문제가 원하는 바입니다.

이 문제는 단지 번호 매기기 문제와 매우 유사합니다. 그냥 배추가 따로 떨어져 있다면, 지렁이가 1마리 더 필요한 것입니다. 이 문제는 단순BFS/DFS이므로 쉽게 풀 수 있습니다.

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

int t;
int row, col, k;
int map[51][51];
bool visit[51][51];
int cnt = 0;

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

void dfs(int r, int c) {
    visit[r][c] = true;

    for(int i = 0; i < 4; i++) {
        int ny = r + dy[i];
        int nx = c + dx[i];
        if(ny < 0 || nx < 0 || ny >= 100 || nx >= 100) return;
        if(!visit[ny][nx] && map[ny][nx] == 1) {
            dfs(ny, nx);
            
        }
    }
}

int main() {
    cin >> t;
    while(t--) {
        cin >> col >> row >> k;
        cnt = 0;
        memset(visit, false, sizeof(visit));
        memset(map, 0, sizeof(map));
        for(int i = 0; i < k; i++) {
            int y, x;
            cin >> x >> y;
            map[y][x] = 1;
        }
        for(int i = 0; i < row; i++) {
            for(int j = 0; j < col; j++) {
                if(!visit[i][j] && map[i][j] == 1) {
                    cnt += 1;
                    dfs(i, j);
                }
            }
        }
        cout << cnt << endl;
    }
    return 0;
}