유기농 배추 1012번 [백준]

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

1012번: 유기농 배추

 

 

유기농 배추는 dfs혹은 bfs로 간단하게 풀어낼 수 있는 문제이다.

배추가 존재하고 이전에 방문하지 않았던 좌표만을 재귀를 통해 진입하는게 코드의 핵심이다.

 

다만 흰배추잎벌레는 뭉쳐있는 배추를 한번에 처리가 가능하므로 처음 dfs함수로 진입할 때에만 cnt의 값을 1 증가시킨다.

 

#include<bits/stdc++.h>
#include<sys/types.h>

using namespace std;
#define endl '\n'
#define fast_io ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define rep(i, j) for(ll i=0;i<j;i++)

int m, n, k;
int matrix[50][50];
int visited[50][50];
int dx[] = {0, 1, -1, 0};
int dy[] = {1, 0, 0, -1};


void dfs(int x, int y) {
    visited[x][y] = true;
    rep(i, 4) {
        int x2 = x + dx[i], y2 = y + dy[i];
        if (x2 >= m || x2 < 0 || y2 >= n || y2 < 0)continue;
        if (matrix[x2][y2] == 1 && !visited[x2][y2]) {
            dfs(x2, y2);
        }
    }
}

void solve() {
    cin >> m >> n >> k;
    rep(i, k) {
        int x, y;
        cin >> x >> y;
        matrix[x][y] = 1;
    }//0, 1, 2
    int cnt = 0;
    rep(i, m) {
        rep(j, n) {
            if (matrix[i][j] == 1 && !visited[i][j]) {
                dfs(i, j);
                cnt++;
            }
        }
    }
    cout << cnt << endl;
    memset(matrix, 0, sizeof(matrix));
    memset(visited, 0, sizeof(visited));
}

int main() {

    fast_io;

    int t;
    cin >> t;
    rep(i, t)solve();
    return 0;
}