[BOJ 1012] 유기농 배추

문제출처

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

문제풀이

/*
* 어디서 많이 본문제라 생각했는데 단지번호붙이기 문제와 같은 문제이다.
* 단순한 dfs/bfs문제인데 상하좌우를 탐색해가면서 배추가 있는 블럭을 일단 다 탐색하면 
* result에 1을 더해 블럭단위를 출력해준다. 기본 dfs문제입니다.
*/

소스코드

#include <iostream>
#include <string.h>
#include <algorithm>
#define MAX 51
 
using namespace std;
int tc, n, m, k;
int map[MAX][MAX];
bool visit[MAX][MAX];
int dx[] = { 0,0,-1,1 };
int dy[] = { -1,1,0,0 };
 
void dfs(int x, int y) {
    for (int i = 0; i < 4; i++) {
        int nx = x + dx[i];
        int ny = y + dy[i];
        if (nx < 0 || ny < 0 || nx >= n || ny >= m)    continue;
 
        if (map[nx][ny] == 1 && !visit[nx][ny]) {
            visit[nx][ny] = 1;
            dfs(nx, ny);
        }
    }
}
 
int main() {
    ios_base::sync_with_stdio(false);    cin.tie(0);
    cin >> tc;
    while (tc--) {
        memset(map, 0, sizeof(map));
        memset(visit, 0, sizeof(visit));
        cin >> n >> m >> k;
        while (k--) {
            int x, y;
            cin >> x >> y;
            map[x][y] = 1;
        }
 
        int result = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (!visit[i][j] && map[i][j] == 1) {
                    dfs(i, j);
                    result++;
                }
            }
        }
        cout << result << endl;
    }
 
    return 0;
}