이번에는 백준 1012번 유기농 배추 문제를 풀어보았습니다.
이 문제는 배추가 심어진 위치들이 주어졌을 때, 서로 인접한 배추 묶음이 몇 개인지를 구하는 문제입니다.
즉, 단순히 배추 개수를 세는 것이 아니라 연결된 그룹의 개수, 다시 말해 연속된 컴포넌트의 개수를 찾는 문제였습니다.
문제 설명
배추밭은 2차원 격자로 주어지고,
1은 배추가 심어진 칸0은 배추가 없는 칸
을 의미합니다.
상하좌우로 인접한 배추들은 하나의 그룹으로 볼 수 있고,
한 그룹당 지렁이 한 마리만 있으면 됩니다.
따라서 이 문제는 결국 배추가 연결된 덩어리가 몇 개인지를 세면 됩니다.
풀이 아이디어
이 문제는 2차원 배열에서 연결된 영역의 개수를 세는 전형적인 문제입니다.
그래서 각 칸을 돌면서
- 배추가 심어져 있고
- 아직 방문하지 않은 칸
을 발견하면, 그 칸을 시작으로 DFS를 수행해서 연결된 배추들을 모두 방문 처리했습니다.
그리고 DFS를 한 번 시작할 때마다 그룹 하나를 찾은 것이므로 카운트를 1 증가시키는 방식으로 해결했습니다.
즉,
- 하나의 DFS 호출 = 하나의 배추 묶음 발견
이라고 볼 수 있습니다.
코드
#include <bits/stdc++.h>
using namespace std;
int T, M, N, K;
vector<vector<int>> farm;
vector<vector<int>> visited;
int dy[4] = {-1, 0, 1, 0};
int dx[4] = {0, 1, 0, -1};
void dfs(int y, int x) {
visited[y][x] = 1;
for (int i = 0; i < 4; i++) {
int ny = y + dy[i];
int nx = x + dx[i];
if (ny >= M || ny < 0 || nx >= N || nx < 0 || visited[ny][nx] || !farm[ny][nx]) continue;
dfs(ny, nx);
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin >> T;
for (int n = 0; n < T; n++) {
cin >> M >> N >> K;
int cnt = 0;
for (int i = 0; i < M; i++) {
farm.push_back(vector<int>(N, 0));
visited.push_back(vector<int>(N, 0));
}
for (int i = 0; i < K; i++) {
int y, x;
cin >> y >> x;
farm[y][x] = 1;
}
for (int i = 0; i < M; i++) {
for (int j = 0; j < N; j++) {
if (farm[i][j] && !visited[i][j]) {
dfs(i, j);
cnt++;
}
}
}
cout << cnt << "\n";
farm.clear();
visited.clear();
}
return 0;
}풀이 흐름
- 테스트 케이스 개수
T를 입력받는다. - 각 테스트 케이스마다 밭 크기
M,N, 배추 개수K를 입력받는다. farm과visited배열을 초기화한다.- 배추가 심어진 위치를
farm에 표시한다. - 전체 격자를 순회하면서 배추가 있고 아직 방문하지 않은 칸을 찾는다.
- 그 칸에서 DFS를 시작해 연결된 배추들을 모두 방문 처리한다.
- DFS를 한 번 시작할 때마다 그룹 개수를 1 증가시킨다.
- 모든 칸을 확인한 뒤 그룹 개수를 출력한다.
구현 포인트
1. 연결된 컴포넌트 개수 세기
이 문제의 핵심은 배추 하나하나를 세는 것이 아니라,
서로 연결된 배추 집합의 개수를 세는 것입니다.
즉, 그래프 관점에서 보면 이 문제는 연결된 컴포넌트의 개수를 찾는 문제라고 볼 수 있습니다.
그래서 DFS나 BFS를 사용해서 한 번에 연결된 영역을 모두 방문 처리하는 방식이 잘 맞습니다.
2. DFS로 연결된 배추 모두 방문 처리
현재 칸에서 상하좌우 네 방향을 확인하면서,
범위 안에 있고, 아직 방문하지 않았고, 배추가 있는 칸이라면 계속 DFS를 진행합니다.
if (ny >= M || ny < 0 || nx >= N || nx < 0 || visited[ny][nx] || !farm[ny][nx]) continue;이 조건문 하나로
- 배열 범위를 벗어나는 경우
- 이미 방문한 경우
- 배추가 없는 경우
를 모두 걸러낼 수 있습니다.
3. 한 번 DFS를 시작할 때마다 그룹 하나
전체 격자를 순회하다가 아직 방문하지 않은 배추를 만났다는 것은,
새로운 배추 묶음을 하나 발견했다는 뜻입니다.
그래서 그 지점에서 DFS를 시작하고, 카운트를 1 증가시켰습니다.
if (farm[i][j] && !visited[i][j]) {
dfs(i, j);
cnt++;
}이 부분이 이 문제의 핵심 로직입니다.
4. 테스트 케이스마다 배열 초기화
이 문제는 테스트 케이스가 여러 개 주어지므로,
각 테스트 케이스가 끝날 때마다 farm과 visited를 초기화해야 합니다.
farm.clear();
visited.clear();이렇게 하지 않으면 이전 테스트 케이스의 정보가 다음 테스트 케이스에 남아 있을 수 있습니다.
