(매일 BOJ) C++ 1012번 유기농 배추

이번 문제는 1012번 유기농 배추 문제이다

이분탐색 다음으로 도장깨기 중인 DFS BFS 유형 2번째 문제이다.

문제 개요

어떤 배추밭이 있다. 서로 인접한 배추들은 해충 방제를 위해 하나의 군락으로 취급된다.
이 군락들을 하나씩 지켜줄 벌레가 최소 몇 마리 필요한지 구하는 문제다.

• 배추는 2차원 좌표상에 심겨 있음
• 상하좌우로 인접한 배추들은 하나의 군락
• 떨어져 있는 배추 군락의 수를 구하면 곧 정답

접근법

 핵심 포인트

• 이 문제는 2차원 배열에서 연결된 덩어리의 개수를 세는 문제다.
• DFS 또는 BFS로 풀 수 있으며, 여기서는 재귀 DFS를 사용한다.

DFS로 접근하는 방법

1. 배추가 심어진 위치(arr[x][y] = true)를 입력으로 받는다.
2. 2차원 배열을 전부 순회하면서:
   • 배추가 있고 && 아직 방문하지 않았다면, DFS를 시작한다.
   • 이 DFS는 연결된 배추들을 전부 방문 처리한다.
   • 하나의 DFS가 끝나면 군락 하나 끝 → 벌레 수 +1
3. 위 과정을 반복해서 전체 군락 수를 구한다.

작성코드

#include <bits/stdc++.h>
using namespace std;


int M,N,K; // 가로길이, 세로길이, 배추의 개수
void DFS(int x, int y, vector<vector<bool>>& arr, vector<vector<bool>>& visit_dfs);

int main(void){
    ios::sync_with_stdio(false); cin.tie(0);
    int T; // 테스트 횟수
    cin >> T;
    
    
     
    for (int i = 0; i < T; i++){
        cin >> M >> N >> K;
        vector<vector<bool>> visit_dfs(M,vector<bool>(N,false));
        vector<vector<bool>> arr(M,vector<bool>(N,false));
        
        for(int j = 0; j < K; j++){
            int x,y;
            cin >> x >> y;
            arr[x][y] = true;
        }

        int result = 0;

        for(int i = 0; i < M; i++){
            for(int j = 0; j < N; j++){
                if(arr[i][j] && !visit_dfs[i][j]){
                DFS(i,j,arr,visit_dfs);
                result += 1;
                }
            }
        }
        cout << result << '\n';
    }
}

void DFS (int x, int y, vector<vector<bool>>& arr, vector<vector<bool>>& visit_dfs){
    visit_dfs[x][y] = true;

    int xxx[4] = {0,0,-1,1};
    int yyy[4] = {-1,1,0,0};
    int x1,y1;
    for(int i = 0; i < 4; i++){
        x1 = x + xxx[i];
        y1 = y + yyy[i];
        if (x1 >= 0 && x1 < M && y1 >= 0 && y1 < N) {
            if (arr[x1][y1] && !visit_dfs[x1][y1]) {
                DFS(x1, y1,arr,visit_dfs);
            }
        }
    }
    
}

DFS 역할	하나의 군락을 모두 방문 처리
visit_dfs	방문 여부를 체크하는 배열
arr	실제 배추가 심어졌는지 여부를 저장
시간복잡도	O(N×M) (밭 전체 순회 + 군락별 DFS 탐색)

더 공부해볼 점

• BFS 방식으로도 풀어보면 좋음 (queue 사용)
• 방문 배열을 전역으로 둘 때와 지역으로 둘 때의 차이점
• DFS가 스택 오버플로우 나는 경우 (배추가 2500개 이상 연결될 때) → 스택 DFS로 변경 가능