[백준/C++] 1012번: 유기농 배추 - 격자 위에서 BFS 덩어리 찾기

1. 문제 정보

• 문제 번호: 1012번
• 문제 이름: 유기농 배추
• 문제 요약: NXM 격자에 배추가 심어져 있다. 상하좌우로 인접한 배추들은 하나의 지렁이로 보호할 수 있다. 총 몇 마리의 지렁이가 필요한지 구하라.

2. 접근 방법 (알고리즘)

 BFS(너비 우선 탐색)를 활용한 군집 탐색

이 문제는 그래프에서 연결 요소(Connected Components)의 개수를 세는 문제입니다.

1. 전수 조사: 격자의 (0, 0)부터 (N-1, M-1)까지 차례대로 방문합니다.
2. 새로운 덩어리 발견: 만약 해당 칸에 배추가 있고(1), 아직 방문하지 않았다면(!visited) 새로운 지렁이가 필요한 시점입니다.
3. 영역 확장: 그 칸을 시작점으로 BFS를 돌려 인접한 모든 배추를 방문 처리(visited = true)합니다. 이 과정이 끝나면 지렁이 한 마리가 커버할 수 있는 모든 영역이 표시됩니다.
4. 카운트: BFS가 한 번 끝날 때마다 지렁이 수를 +1 해줍니다.

 

3. 핵심 포인트: "초기화의 중요성" ⚠️

이 문제는 여러 개의 테스트 케이스(T)가 주어집니다. 여기서 가장 많이 하는 실수가 이전 테스트 케이스의 데이터가 배열에 남아있는 것입니다.

<cstring>과 memset

사용자가 해결한 핵심 열쇠죠! 각 테스트 케이스가 시작될 때마다 ground 배열과 visited 배열을 깨끗하게 비워줘야 합니다.

• memset(target, value, size): 메모리 블록을 특정 값으로 한꺼번에 채워주는 함수입니다.
• 0이나 false로 초기화할 때 매우 빠르고 효율적입니다.

 

4. 코드 구현

#include <iostream>
#include <queue>
#include <cstring> // memset을 사용하기 위한 라이브러리

using namespace std;

int M, N, K;
int ground[50][50];
bool visited[50][50];
int dx[4] = {1, -1, 0, 0}; // 상하좌우 탐색을 위한 방향 벡터
int dy[4] = {0, 0, 1, -1};

void bfs(int x, int y) {
    queue<pair<int,int>> q;
    q.push({x,y});
    visited[x][y] = true;

    while(!q.empty()) {
        int cx = q.front().first;
        int cy = q.front().second;
        q.pop();

        for(int i=0; i<4; i++) {
            int nx = cx + dx[i];
            int ny = cy + dy[i];

            // 격자 범위 내에 있고, 배추가 있으며, 방문하지 않은 경우
            if(nx >= 0 && nx < N && ny >= 0 && ny < M) {
                if(ground[nx][ny] == 1 && !visited[nx][ny]) {
                    visited[nx][ny] = true;
                    q.push({nx,ny});
                }
            }
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    cin >> T;
    while(T--) {
        cin >> M >> N >> K;
        
        // 1. 매 테스트 케이스마다 배열 초기화 (가장 중요!)
        memset(ground, 0, sizeof(ground));
        memset(visited, false, sizeof(visited));

        for(int i=0; i<K; i++) {
            int x, y;
            cin >> x >> y;
            ground[y][x] = 1; // y를 행(세로), x를 열(가로)로 매칭
        }

        int wormCount = 0;
        // 2. 격자 전체를 순회하며 BFS 시작점 찾기
        for(int i=0; i<N; i++) {
            for(int j=0; j<M; j++) {
                if(ground[i][j] == 1 && !visited[i][j]) {
                    bfs(i,j);
                    wormCount++; // BFS가 호출될 때마다 지렁이 한 마리 추가
                }
            }
        }
        cout << wormCount << "\n";
    }
    return 0;
}

 

 

5. 배운 점 & 회고 (TIL) ✍️

① 다중 테스트 케이스는 "무조건 초기화"

"이게 왜 안 되지?" 싶을 땐 초기화 문제입니다. memset 사용법을 익힐 수 있었습니다.

② 좌표 평면과 배열 인덱스의 혼동

문제에서는 가로(M), 세로($N$)로 주어지는데, 우리는 보통 배열을 arr[row][col] 순서로 씁니다. 즉, 배열의 행이 세로(N), 열이 가로(M)**가 됩니다. 입력받을 때 ground[y][x]로 넣어주는 디테일이 아주 중요했습니다.

③ BFS의 범용성

'바이러스' 문제처럼 인접 리스트로 푸는 그래프나, 이번 문제처럼 격자(Grid) 위에서 푸는 문제나 "방문 처리로 중복을 막는다"는 핵심 원리는 똑같다는 걸 체감했습니다.