[BOJ] #1012 유기농 배추

시간 제한	메모리 제한	정답 비율
1 초	512 MB	33.788%

 

1012번: 유기농 배추

문제

해충 방지에 효과적인 배추흰지렁이를 구입했다. 이 지렁이는 배추근처에 서식하며 해충을 잡아 먹음으로써 배추를 보호한다. 특히, 어떤 배추에 배추흰지렁이가 한 마리라도 살고 있으면 이 지렁이는 인접한 다른 배추로 이동할 수 있어, 그 배추들 역시 해충으로부터 보호받을 수 있다.

배추들이 모여있는 곳에는 배추흰지렁이가 한 마리만 있으면 되므로 서로 인접해있는 배추들이 몇 군데에 퍼져있는지 조사하면 총 몇 마리의 지렁이가 필요한지 알 수 있다. 

각 테스트 케이스에 대해 필요한 최소의 배추흰지렁이 마리 수를 출력하라.

해결방안

일반적인 DFS를 통해서 쉽게 풀 수 있었다. chk배열과 입력으로 받은 arr배열을 이용하여 체크가 되어있지 않고, 배추가 있다면 DFS를 돌게끔 하여 몇 개의 구역이 나뉘어 있는지 찾아서 필요한 배추흰지렁이의 수를 출력하였다.

메모리	시간
2012 KB	0 ms

#include<iostream>
#include<string.h>
using namespace std;
#define F(x,y,u,p) for(int x = 0; x<u; x++)for(int y = 0; y<p; y++)
int t, n, m, k, arr[55][55], chk[55][55], dx[] = { 0,1,0,-1 }, dy[] = { 1,0,-1,0 }, cnt;
void dfs(int r, int c) {
    chk[r][c] = 1;
    for (int i = 0; i < 4; i++) {
        int nr = r + dx[i], nc = c + dy[i];
        if (nr < 0 || nr >= n || nc < 0 || nc >= m || chk[nr][nc] || !arr[nr][nc]) continue;
        chk[nr][nc] = 1;
        dfs(nr, nc);
    }
}
int main() {
    scanf("%d", &t);
    while (t--) {
        scanf("%d %d %d", &n, &m, &k);
        for (int i = 0, a, b; i < k; i++) {
            scanf("%d %d", &a, &b);
            arr[a][b] = 1;
        }
        F(i, j, n, m) {
            if (!chk[i][j] && arr[i][j]) {
                dfs(i, j); cnt++;
            }
        }
        printf("%d\n", cnt);
        cnt = 0; 
        memset(arr, 0, sizeof(arr));
        memset(chk, 0, sizeof(chk));
    }
    return 0;
}