[c, c++] 백준 1012번 - 유기농 배추

백준 1012번 유기농 배추 문제

문제 링크 : https://www.acmicpc.net/problem/1012

문제로 바로 이동 (클릭해주세요)

문제 해석 및 설명

인접한 배추에 배추흰지렁이가 한 마리라도 살고 있으면 해충으로 보호 받을수 있다. ( 이 내용이 중요 )

이 경우 위에 주어진 TC에서 (1은 배추의 위치를 뜻함) 지렁이는 5마리가 살고 있습니다.

왜 5마리가 살고 있는지 그림으로 설명 드리겠습니다.

인접해있기 때문에 빨간색으로 표기한 위치에 지렁이가 1마리씩 있을 수 있습니다.

그럼 배열을 탐색하면서 1을 만난 경우 상 하 좌 우 탐색을 하면서 1의 값을 0으로 만들어 버리면 쉽게 문제를 해결 할 수 있습니다. 

탐색 방법은 재귀문을 통해 탐색하는 것이 코드 구현이 간단해집니다.

지렁이 count 하는 방법

if (cabbage[i][j] == 1) {
   count++;
   searchCabbage(i, j);
}

배열을 탐색하면서 현재 위치의 배열하는 값이 1이라면 지렁이의 수를 count를 1씩 증가해주고

재귀문을 호출하였습니다.

탐색 방법

void searchCabbage(int n, int m) {
    if (cabbage[n][m] == 1) {
        cabbage[n][m] = 0;
    }
 
    if (cabbage[n][m + 1] == 1) {
        cabbage[n][m + 1] = 0;
        searchCabbage(n, m + 1);
    }
    if (cabbage[n][m - 1] == 1) {
        cabbage[n][m - 1] = 0;
        searchCabbage(n, m - 1);
    }
    if (cabbage[n + 1][m] == 1) {
        cabbage[n + 1][m] = 0;
        searchCabbage(n+1, m);
    }
    if (cabbage[n - 1][m] == 1) {
        cabbage[n - 1][m] = 1;
        searchCabbage(n-1, m);
    }
}

cabbage 배열의 상 하 좌 우 의 값이 1이면 0으로 만들어 버리고 해당 index로 이동 하는 것을 반복하면 됩니다. 

그럼 인접한 배열은 모두 0으로 채워지게 됩니다.

전체 소스 

#include <iostream>
using namespace std;
 
int cabbage[51][51];
 
int M;    // 가로
int N;    // 세로
int K;    // 갯수
 
void init() {
    for (int i = 0; i < 51; i++) {
        for (int j = 0; j < 51; j++)
            cabbage[i][j] = 0;
    }
}
 
void searchCabbage(int n, int m) {
    if (cabbage[n][m] == 1) {
        cabbage[n][m] = 0;
    }
 
    if (cabbage[n][m + 1] == 1) {
        cabbage[n][m + 1] = 0;
        searchCabbage(n, m + 1);
    }
    if (cabbage[n][m - 1] == 1) {
        cabbage[n][m - 1] = 0;
        searchCabbage(n, m - 1);
    }
    if (cabbage[n + 1][m] == 1) {
        cabbage[n + 1][m] = 0;
        searchCabbage(n+1, m);
    }
    if (cabbage[n - 1][m] == 1) {
        cabbage[n - 1][m] = 1;
        searchCabbage(n-1, m);
    }
}
 
int main() {
    int tc;
    cin >> tc;
    
    for (int tt = 0; tt < tc; tt++) {
        init();
        cin >> M >> N;
        cin >> K;
 
        for (int kk = 0; kk < K; kk++) {
            int m;
            int n;
            cin >> m;
            cin >> n;
            
            cabbage[n][m] = 1;
        }
 
        int count = 0;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (cabbage[i][j] == 1) {
                    count++;
                    searchCabbage(i, j);
                }
            }
        }
        cout << count << endl;
    }
 
    return 0;
}