[C++] BaekJoon 1012 유기농 배추

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

---

이 문제는 연결된 영역을 찾는 문제로 볼 수 있다. 

배추들이 인접해있는 영역을 찾고 각 영역에 대해 최소한의 배추흰지렁이의 수를 계산하면 된다. 

 

코드

#include <iostream>
#include <vector>

using namespace std;

void dfs(vector<vector<int>>& field, int x, int y, int m, int n) {
    //값이 음수이거나, 행렬을 벗어나거나, 이미 방문한 노드, 즉 배추가 없다면 탐색하지 않는다.
    if (x < 0 || x >= m || y < 0 || y >= n || field[x][y] == 0) {
        return;
    }

    field[x][y] = 0; // 이미 방문한 배추는 0으로 표시

    // 상하좌우로 이동하며 배추가 있는지 확인
    dfs(field, x + 1, y, m, n);
    dfs(field, x - 1, y, m, n);
    dfs(field, x, y + 1, m, n);
    dfs(field, x, y - 1, m, n);
}

int countCabbageWorms(vector<vector<int>>& field) {
    int m = field.size(); // 행의 수
    int n = field[0].size(); // 열의 수

    int worms = 0; // 배추흰지렁이 수

    // 전체 배추 밭을 탐색하며 배추 영역을 찾음
    for (int i = 0; i < m; ++i) {
        for (int j = 0; j < n; ++j) {
            if (field[i][j] == 1) { // 아직 방문하지 않은 배추를 발견하면
                dfs(field, i, j, m, n); // 해당 배추 영역을 모두 탐색
                worms++; // 배추흰지렁이 수 증가
            }
        }
    }

    return worms;
}

int main() {
    int T; // 테스트 케이스의 개수
    cin >> T;

    while (T--) {
        int M, N, K; // 가로길이, 세로길이, 배추 개수
        cin >> M >> N >> K;

        // 배추 밭 초기화, 배추 밭을 모두 0으로 초기화
        vector<vector<int>> field(M, vector<int>(N, 0));

        // 배추 위치 입력 및 표시
        for (int i = 0; i < K; ++i) {
            int X, Y;
            cin >> X >> Y;
            field[X][Y] = 1;
        }

        int worms = countCabbageWorms(field);
        cout << worms << "\n";
    }

    return 0;
}

설명

DFS로 계산하였다. 

 

DFS 함수 설명:

깊이 우선을 탐색을 수행하는 함수이다.

시작점으로부터 연결된 모든 배추들을 탐색한다. 

field는 배추 밭을 나타내는 2차원 벡터이고 (x,y) 는 현재 위치를 나타낸다.

m,n은 각각 배추 밭의 행과 열의 개수를 나타낸다. 

함수가 호출되면 현재 위치 (x,y)에서 상하좌우로 이동하며 배추가 있는지 확인. 

값이 음수이거나, 행렬을 벗어나거나, 이미 탐색한 노드, 배추가 없는 땅이면 탐색을 진행하지 않는다. 

이미 방문한 배추는 0으로 표시, 중복해서 세지 않도록 한다.

 

countCabbageWorms 함수 설명:

주어진 배추 밭에서 배추흰지렁이의 최소 개수를 계산하는 함수이다. 

배추 밭의 행의 수를 m, 열의 수를 n으로 저장한다. 

그 후, 배추 밭의 모든 위치를 탐색하면서 배추가 있는 곳을 찾는다.

만약 현재 위치에 배추가 있다면, dfs 함수를 호출하여 해당 배추 영역을 모두 탐색한다.

배추 영역을 모두 탐색한 후에는 배추흰지렁이의 수를 증가시킨다.

모든 배추 영역을 탐색하고 나면, 총 배추흰지렁이의 수를 반환한다. 

 

이러한 방식으로 dfs 함수는 각 배추 영역을 찾고, countCabbageWorms 함수는 모든 배추 영역을 탐색하여 배추흰지렁이의 수를 계산한다.