[C++] 백준 1012번 유기농 배추

 

1) 문제설명

 

백준 Online Judge 1012번 유기농 배추

백준 Online Judge 1012번 유기농 배추

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

1012번: 유기농 배추

 

2) 아이디어

 

DFS를 사용하여 1이 연속으로 되어있는 구간일 경우 카운트를 세 주었다.

 

3) 코드

 

#include<iostream>
#include<queue>
#include<deque>
#include<string.h>
#include<math.h>
#include<cmath>
#include<stack>
#include<algorithm>

using namespace std;

priority_queue <int,vector<int>,greater<int>> v; // 우선순위 큐를 오름차순으로 정렬

int arr[55][55];
int cnt = 0;

void dfs(int x, int y, int m, int n) {
    if (x < 0 || y < 0 || x >= m || y >= n) { // 범위에서 벗어날 경우 return
        return;
    }
    
    if (arr[x][y] == 1) { // 1인 단지일때
        arr[x][y] = 0; // 0으로 초기화 후
        cnt++; // 갯수를 세어준다
        dfs(x - 1, y, m ,n);
        dfs(x + 1, y, m ,n);
        dfs(x, y - 1, m, n);
        dfs(x, y + 1, m, n);
    }
 
}

int main() {
    int n, m, t ,k;
    
    cin >> t;
    for (int i = 0; i < t; i++) {
        cin >> m >> n >> k;
        int cnt = 0;
        for (int j = 0; j < k; j++) {
            int x, y;
            cin >> x >> y;
            arr[x][y] = 1;
        }
        for (int l = 0; l < m; l++) {
            for (int j = 0; j < n; j++) {
                if (arr[l][j] == 1) {
                    dfs(l, j, m, n);
                    cnt++;
                }
            }
        }
        cout << cnt << endl;
    }

}