1012번-유기농 배추

중요 지식

---

DFS - 배추가 모여있는 곳에서 어느 땅이 속해있는지 탐색해야 한다 

fill() - 테스트 케이스를 재 실행하기 위해 프로그램 세팅을 초기화시켜야 한다 

 

코드

---

#include <iostream>
#include <algorithm>

using namespace std;

int N, M;
int farm[51][51] = {0};
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};

void DFS(int x, int y){
    farm[x][y] = 0;

    for(int i = 0; i < 4; i++){
        int nx = x + dx[i];
        int ny = y + dy[i];
        
        if((nx >= 0 && nx <= N) && (ny >= 0 && ny <= M) && farm[nx][ny] == 1){
            DFS(nx, ny);
        }
    }
}

int main(){
    int T, K;
    int X, Y;
    int count;

    cin >> T;

    for(int i = 0; i < T; i++){
        cin >> N >> M >> K;

        fill(&farm[0][0], &farm[N-1][M], 0);
        count = 0;

        for(int j = 0; j < K; j++){
            cin >> X >> Y;
            farm[X][Y] = 1;
        }

        for(int xi = 0; xi < N; xi++){
            for(int yj = 0; yj < M; yj++){
                if(farm[xi][yj]){
                    count++;
                    DFS(xi, yj);
                }
            }
        }

        cout << count << endl;
    }

    return 0;
}

풀이

---

1. 밭 전체를 나타내는 farm배열을 만들고, 배추가 있는 좌표를 저장한다.

2. 밭 전체를 순회하면서 배추가 있다면 주변에 근접한 배추가 있는지 탐색한다  -DFS

3. 끝