[BaekJoon][1012] 유기농 배추

BAEKJOON ONLINE JUDGE

1012 유기농 배추

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

labeling 문제

15분

#include <stdio.h>
 
int width, height;
int map[51][51];
int label[51][51];
 
void init()
{
    int i, j;
 
    for (i = 0; i <= height; i++) {
        for (j = 0; j <= width; j++) {
            map[i][j] = label[i][ j] = 0;
        }
    }
}
 
void dfs(int y, int x)
{
    int i;
    int dy[4] = { 0, 0, -1, 1 };
    int dx[4] = { -1, 1, 0, 0 };
    int nexty, nextx;
    
    for (i = 0; i < 4; i++) {
        nexty = y + dy[i];
        nextx = x + dx[i];
 
        if (nexty >= 0 && nexty < height && nextx >= 0 && nextx < width) {
            if (map[nexty][nextx] == 1 && label[nexty][nextx] == 0) {
                label[nexty][nextx] = label[y][x];
                dfs(nexty, nextx);
            }
        }
    }
}
 
int labeling()
{
    int count = 1;
    int i, j;
 
    for (i = 0; i < height; i++) {
        for (j = 0; j < width; j++) {
            if (map[i][j] == 1 && label[i][j] == 0) {
                label[i][j] = count++;
                dfs(i, j);
            }
        }
    }
 
    return count - 1;
}
 
int main()
{
    int nCount;
    int i, k;
    int x, y;
 
    scanf("%d", &nCount);
 
    while (nCount--) {
 
        scanf("%d %d %d", &width, &height, &k);
 
        for (i = 0; i < k; i++) {
            scanf("%d %d", &x, &y);
            map[y][x] = 1;
        }
 
        printf("%d\n", labeling());
 
        init();
    }
 
    return 0;
}