[C++] 백준 알고리즘 1012번 (유기농 배추)

문제

---

이번에 다뤄볼 문제는 1012번 문제 '유기농 배추'입니다.

유기농 배추 문제에서 연습해야하는 key-point는재귀함수입니다.

 

재귀함수란 어떤 함수에서 자신을 다시 호출하여 작업울 수행하는 방식의 함수를 뜻합니다.

배추가 최초 확인 되었을 경우 b_count값을 증가시켜준뒤 재귀로 들어가 인접한 배추들을
다시 탐색하지 않도록 2로 값을 바꿔줍니다.

 

아래 해답 코드를 보면 더 쉽게 이해할 수 있으실 겁니다.

---

 

코드(C++)

#include <iostream>
using namespace std;
 
int map[51][51] = {0};
 
int dirX[4] = {0,0,-1,1};
int dirY[4] = {-1,1,0,0};
 
 
int xx = 0, yy = 0;
int t, m, n, k;
int b_count = 0;
 
void bachu(int x, int y) {
    map[x][y] = 2;
 
    for (int i = 0; i < 4; i++) {
        xx = x + dirX[i];
        yy = y + dirY[i];
 
        if (map[xx][yy] == 0 || map[xx][yy] == 2 || xx<0 || xx>m || yy<0 || yy>n) continue;
        if (map[xx][yy] == 1) {
            bachu(xx,yy);
        }
    }
}
 
int main() {
 
    int x, y;
 
    cin >> t;
    for (int i = 1; i <= t; i++) {
        cin >> m >> n >> k;
         
        for (int j = 1; j <= k; j++) {
            cin >> x >> y;
            map[x][y] = 1;
        }
 
        for (int p = 0; p < m; p++) {
            for (int r = 0; r < n; r++) {
                if (map[p][r] == 1) {
                    b_count++;
                    bachu(p,r);
                }
            }
        }
        cout << b_count << endl;
        b_count = 0;
        map[51][51] = {0};
    }
 
    return 0;
}