백준 1012번 유기농 배추

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

전형적인 dfs 혹은 bfs 로 풀수있는 문제이다.
딱히 풀이방법을 적을 것도 없이 인접한 배추끼리는 에벌레 1마리로 벌레를 예방가능하므로
인접한 배추들끼리 그룹을 지어 최소로 필요한 에벌레의 갯수를 구할 수 있다.


#include <iostream>
#define MAX 50
using namespace std;
int m, n;
int dx[4] = {0, -1, 0, 1};
int dy[4] = {-1, 0, 1, 0};
bool isInner(int x, int y) {
    return (x >= 0 && x < n && y >= 0 && y < m);
}
// 4방향 탐색하면서 인접한 배추들의 그룹을 만듬
void makeGroup(int (*map)[MAX + 1], int (*group)[MAX + 1], int x, int y, int gNum) {
    for (int i = 0; i < 4; ++i) {
        int nx = x + dx[i];
        int ny = y + dy[i];
        
        if (isInner(nx, ny) && map[nx][ny] == 1 && group[nx][ny] == 0) {
            group[nx][ny] = gNum;
            makeGroup(map, group, nx, ny, gNum);
        }
    }
}
int main()
{
    int T, k, x, y;
    scanf("%d", &T);
    for (int i = 0; i < T; ++i) {
        int gNum = 1;
        int map[MAX + 1][MAX + 1] = {0, };
        int group[MAX + 1][MAX + 1] = {0, };
        
        // 배추 표시
        scanf("%d %d %d", &m, &n, &k);
        for (int j = 0; j < k; ++j) {
            scanf("%d %d", &y, &x);
            map[x][y] = 1;
        }
        
        for (int row = 0; row < n; ++row) {
            for (int col = 0; col < m; ++col) {
                // 배추 && 그룹 미지정일 때만 그룹만들기 수행
                if (map[row][col] == 1 && group[row][col] == 0) {
                    makeGroup(map, group, row, col, gNum);
                    gNum++;
                }
            }
        }
        
        // 그룹의 갯수 - 1 이 최소 애벌레의 갯수
        printf("%d\n", gNum - 1);
    }
    
    return 0;
}