[Baekjoon(백준)][1012번] 유기농 배추(C++)

안녕하세요! 오늘은 코딩테스트 문제 중 하나인 "유기농 배추" 문제를 해결하는 방법에 대해 설명하려고 합니다. 이 문제에서는 M×N 크기의 배추밭에서 서로 인접한 배추들이 몇 그룹으로 나뉘어 있는지 찾는 문제입니다. 문제를 해결하는 과정과 코드를 자세히 알아보겠습니다.

문제링크:

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

1012번: 유기농 배추

문제 개요

"유기농 배추" 문제는 M×N 크기의 배추밭에서 서로 인접한 배추들이 몇 그룹으로 나뉘어 있는지 찾는 문제입니다. 이때, 상하좌우로 인접해 있는 배추들을 하나의 그룹으로 간주합니다. 문제의 목표는 필요한 최소한의 배추흰지렁이 수를 계산하는 것입니다.

해결 방법

이 문제는 깊이 우선 탐색(DFS) 알고리즘을 사용하여 해결할 수 있습니다. 각 배추 위치를 방문할 때마다 상하좌우 인접한 배추들을 재귀적으로 탐색하며, 이를 통해 배추 그룹의 전체 범위를 파악합니다. 새로운 배추 그룹이 시작될 때마다 카운터를 증가시켜 전체 그룹의 수를 찾습니다.

코드 구현

#include <iostream>
#include <vector>
#include <queue>

using namespace std;
int c = 0;
int n, m, k = 0;
int table[55][55];
bool visited[55][55];
int dy[] = { -1,0,1,0 };
int dx[] = { 0,1,0,-1 };

void dfs(int y, int x) 
{
    visited[y][x] = true;
    for (int i = 0; i < 4; i++) {
        int ny = y + dy[i];
        int nx = x + dx[i];
        // 범위 체크 및 배추가 있는지, 방문 여부 확인
        if (ny >= 0 && nx >= 0 && ny < n && nx < m && table[ny][nx] == 1 && !visited[ny][nx]) {
            dfs(ny, nx); // 인접한 배추 탐색
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> c; // 테스트 케이스 수
    while (c--)
    {
        cin >> m >> n >> k; // 배추밭의 크기 및 배추 수
        fill(&table[0][0], &table[0][0] + 55 * 55, 0); // 배추밭 초기화
        fill(&visited[0][0], &visited[0][0] + 55 * 55, false); // 방문 배열 초기화

        for (int i = 0; i < k; i++) {
            int a, b = 0;
            cin >> a >> b; // 배추 위치 입력
            table[b][a] = 1;
        }

        int count = 0; // 필요한 배추흰지렁이 수
        for (int y = 0; y < n; y++) {
            for (int x = 0; x < m; x++) {
                if (table[y][x] == 1 && !visited[y][x]) {
                    count++; // 새로운 배추 그룹 발견
                    dfs(y, x); // 해당 배추 그룹 탐색
                }
            }
        }
        cout << count << "\n"; // 결과 출력
    }
}

코드 설명

이 코드는 각 배추밭에 대해 DFS를 사용하여 배추 그룹을 탐색합니다. 배추가 있는 위치에서 DFS 탐색을 시작하여 상하좌우 인접한 배추를 모두 방문합니다. 새로운 배추 그룹을 찾을 때마다 카운터를 증가시켜 필요한 배추흰지렁이 수를 계산합니다.

결론

"유기농 배추" 문제는 DFS를 사용하여 2차원 그리드 내에서 연결된 구성 요소를 찾는 고전적인 문제입니다. DFS 알고리즘을 이해하고 재귀적으로 구현하는 능력이 중요합니다.