[백준 1012] 유기농 배추 (C, DFS)

문제 링크

1012번: 유기농 배추

전형적인 DFS, BFS 기본 문제. C로 리마인드할겸..

 

가로, 세로 입력은 순서 헷갈리지 않게 항상 주의하자~

 

 

/*
    2020-01-05
    유기농배추
    https://www.acmicpc.net/problem/1012
*/
 
#include <stdio.h>
 
int M, N, K, ans;
int map[51][51], visit[51][51];
 
int dy[] = { -1,1,0,0 };
int dx[] = { 0,0,-1,1 };
 
void init(int *, int size);
void dfs(int y, int x);
 
int main(void) {
 
    int testcase;
    scanf("%d", &testcase);
 
    for (int i = 0; i < testcase; i++)
    {
        ans = 0;
        init(map, sizeof(map) / 4);
        init(visit, sizeof(map) / 4);
 
        scanf("%d %d %d", &M, &N, &K);
 
        for (int i = 0; i < K; i++)
        {
            int x, y;
            scanf("%d %d", &x, &y);
            map[y][x] = 1;
        }
 
        for (int i = 0; i < N; i++)
        {
            for (int j = 0; j < M; j++)
            {
                if (map[i][j] == 1 && !visit[i][j]) {
                    dfs(i, j);
                    ans++;
                }
            }
        }
 
        printf("%d\n", ans);
    }
 
    return 0;
}
 
void dfs(int y, int x) {
 
    visit[y][x] = 1;
 
    for (int i = 0; i < 4; i++)
    {
        int ny = y + dy[i];
        int nx = x + dx[i];
 
        if (ny < 0 || nx < 0 || ny >= N || nx >= M) continue;
 
        if (map[ny][nx] == 1 && !visit[ny][nx])
            dfs(ny, nx);
    }
 
}
 
void init(int *arr, int size) {
    for (int i = 0; i < size; i++)
    {
        arr[i] = 0;
    }
}