백준) 1012 유기농 배추

유기농 배추

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

DFS의 기본적인 버전이다.

재귀적으로 돌아가는 과정만 이해하면 DFS만큼 편한게 없다.

코드는 다음과 같다.

#include <stdio.h>
 
int t;
int m, n, k;
int x, y;
int ans;
 
int map[50][50];
int dir[4][2] = { {-1,0},{1,0},{0,-1},{0,1} };
 
void dfs(int x, int y) {
    map[x][y] = 0;
 
    for (int i = 0; i < 4; ++i) {
        int xx = x + dir[i][0];
        int yy = y + dir[i][1];
 
        if (xx < 0 || yy < 0 || xx >= n || yy >= m)
            continue;
 
        if (map[xx][yy] != 1)
            continue;
 
        dfs(xx, yy);
    }
}
 
int main() {
    scanf("%d", &t);
 
    while (t--) {
        scanf("%d %d %d", &m, &n, &k);
 
        ans = 0;
        for (int i = 0; i < n; ++i)
            for (int j = 0; j < m; ++j)
                map[i][j] = 0;
 
        for (int i = 0; i < k; ++i) {
            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) {
                    ans++;
                    dfs(i, j);
                }
            }
        }
            
 
        printf("%d\n", ans);
    }
 
    return 0;
}