[백준] 1012번 유기농 배추

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

1012번: 유기농 배추

1. 문제 접근

MxN 밭에서 1로표시된 군집의 갯수를 세는 문제이다. 여기서 군집이란 문제의 설명처럼 인접한 배추들을 말한다. 이러한 인접한 원소를 다루는 문제는 BFS나 DFS를 생각할 수 있는데 해당문제는 어느것을 사용하여도 풀수 있으나 필자는 재귀함수를 이용한 DFS를 사용하였다.

 

시간복잡도 계산

MxN 밭의 모든 위치에서 인접한 방향을 검색해야하는 경우가 최악의 경우이므로 시간복잡도는 아래와 같이 계산해 볼 수 있다. 이는 주어진시간 1초동안 너무나 충분한 계산 횟수이기에 위 방법을 사용하여 문제를 풀어보았다.

시간복잡도 = M x N x 4(인접한 방향 갯수) = 10,000

 

 

 

2. 코드

#include<iostream>
using namespace std;

#define MAX_MN 50

int cir_m[4] = { -1, 0, 1, 0 };
int cir_n[4] = { 0, 1, 0, -1 };

int check(int loc[][MAX_MN], int checked[][MAX_MN], int m, int n, int mSize, int nSize) {
    if (m < 0 || n < 0 || m >= mSize || n >= nSize)
        return 0;
    if (loc[m][n] == 0 || checked[m][n] == 1)
        return 0;

    checked[m][n] = 1;
    for (int i = 0; i < 4; i++)
        check(loc, checked, m + cir_m[i], n + cir_n[i], mSize, nSize);

    return 1;
}

void init(int loc[][MAX_MN], int checked[][MAX_MN], int m, int n) {
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            loc[i][j] = 0;
            checked[i][j] = 0;
        }
    }
}

int main() {
    int T;
    int M, N, K;
    int cabLoc[MAX_MN][MAX_MN] = { 0, };
    int checked[MAX_MN][MAX_MN] = { 0, };

    cin >> T;
    for (int t = 0; t < T; t++) {
        cin >> M >> N >> K;
        init(cabLoc, checked, M, N);
        for (int i = 0; i < K; i++) {
            int mK, nK;
            cin >> mK >> nK;
            cabLoc[mK][nK] = 1;
        }

        int bugCount = 0;
        for (int i = 0; i < M; i++)
            for (int j = 0; j < N; j++)
                if (check(cabLoc, checked, i, j, M, N) == 1)
                    bugCount++;

        cout << bugCount << endl;
    }

    return 0;
}