[Graph] 1012번 - 유기농 배추(34일차)

#include <iostream>
//memset 사용
#include <cstring>
#include <algorithm>

using namespace std;

//가로길이, 세로길이, 배추 개수, 배추밭 개수
int m, n, k, length;

//배추 군집을 탐색하기 위한 dfs 함수(배추밭, 방문기록, y좌표, x좌표, 배추 군집 번호)
int dfs(int **cabbage, int **visit, int y, int x, int number){
    //좌상우하 탐색을 위한 좌표 선언
    int dy[4] = {0, -1, 0, 1};
    int dx[4] = {-1, 0, 1, 0};
    //해당 탐색지점 좌표의 visit을 배추 군집 번호로 저장
    visit[y][x] = number;
    //좌상우하에 대해
    for (int i = 0; i < 4; i++) {
        //새로운 좌표 생성
        int nx = x + dx[i];
        int ny = y + dy[i];
        //새로운 좌표가 배추밭 안에 있을 때
        if (nx < 0 || nx >= m || ny < 0 || ny >= n)
            continue;
        //새로운 y,x좌표가 방문된 적이 없고, 배추가 있을 때
        if (cabbage[ny][nx] == 1 && visit[ny][nx] == 0) {
            //재귀를 이용해 재탐색 시작
            dfs(cabbage, visit, ny, nx, number);
        }
    }
}


int main(){
    //배추밭 개수 입력
    cin >> length;
    //각 배추밭에 대해 반복
    for(int i=0; i<length; i++){
        //배추 군집 수 세는 변수
        int cnt = 0;
        //배추밭의 x길이 y길이, 배추 개수를 입력
        cin >> m >> n >> k;

        //배추밭과 방문기록 2차원 배열 동적할당 후 0으로 초기화
        int **cabbage = new int *[n];
        int **visit = new int *[n];

        for(int i=0; i<n; i++){
            cabbage[i] = new int[m];
            visit[i] = new int[m];
            memset(cabbage[i], 0, sizeof(int)*m);
            memset(visit[i], 0, sizeof(int)*m);
        }

        //배추밭 기록
        for(int j=0; j<k; j++){
            int y, x;
            cin >> x >> y;
            cabbage[y][x] = 1;
        }

        //배추밭 모든 위치에 대해
        for(int i=0; i<n; i++){
            for(int j=0; j<m; j++){
                //배추가 있고 방문된 적이 없으면
                if(visit[i][j] == 0 && cabbage[i][j] == 1){
                    //배추 군집 수 추가 후
                    cnt++;
                    //해당 위치에서 dfs 탐색
                    dfs(cabbage, visit, i, j, cnt);
                }
            }
        }
        //배추 군집의 개수(지렁이가 필요한 수) 출력
        cout << cnt;
    }
}