이번에는 백준 2583번 영역 구하기 문제를 풀어보았습니다.
이 문제는 직사각형으로 채워진 부분을 제외한 나머지 영역이 몇 개로 나뉘는지 구하고, 각 영역의 넓이까지 출력해야 하는 문제입니다.
즉, 단순히 연결된 컴포넌트의 개수만 세는 것이 아니라, 각 컴포넌트의 크기도 함께 구해야 했습니다.
문제 설명
M x N 크기의 모눈종이에 K개의 직사각형이 주어집니다.
이 직사각형 내부를 제외한 나머지 부분이 몇 개의 분리된 영역으로 나뉘는지 구하고, 각 영역의 넓이를 오름차순으로 출력하면 됩니다.
즉, 문제를 그래프처럼 보면
- 직사각형이 칠해진 칸은 이동할 수 없는 칸
- 나머지 칸은 이동 가능한 칸
으로 볼 수 있고,
이 이동 가능한 칸들이 몇 개의 연결된 영역으로 나뉘는지와 그 크기를 구하는 문제입니다.
풀이 아이디어
이 문제는 결국 인접한 컴포넌트의 개수와 각 컴포넌트의 넓이를 구하는 문제입니다.
그래서 먼저 전체 종이를 1로 초기화한 뒤,
직사각형이 차지하는 부분을 0으로 바꾸었습니다.
그 다음 전체 배열을 순회하면서
- 아직 방문하지 않았고
- 이동 가능한 칸(
1)인 경우
DFS를 시작했습니다.
이때 DFS는 단순 방문 처리만 하는 것이 아니라,
현재 연결된 영역의 크기까지 함께 계산해야 했습니다.
그래서 void가 아니라 int를 반환하는 DFS를 사용했고, size 인자를 하나씩 증가시키며 넘기도록 구현했습니다.
코드
#include <bits/stdc++.h>
using namespace std;
int M, N, K;
vector<vector<int>> inp_map;
vector<vector<int>> visited;
int dy[4] = {-1, 0, 1, 0};
int dx[4] = {0, 1, 0, -1};
vector<int> result;
int dfs(int y, int x, int size) {
visited[y][x] = 1;
for (int i = 0; i < 4; i++) {
int ny = y + dy[i];
int nx = x + dx[i];
if (ny < 0 || nx < 0 || ny >= M || nx >= N || visited[ny][nx] || !inp_map[ny][nx])
continue;
size = dfs(ny, nx, size + 1);
}
return size;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin >> M >> N >> K;
for (int i = 0; i < M; i++) {
inp_map.push_back(vector<int>(N, 0));
visited.push_back(vector<int>(N, 0));
for (int j = 0; j < N; j++) {
inp_map[i][j] = 1;
visited[i][j] = 0;
}
}
for (int i = 0; i < K; i++) {
int sty, stx;
int edy, edx;
cin >> stx >> sty >> edx >> edy;
for (int j = 0; j < edy - sty; j++) {
for (int k = 0; k < edx - stx; k++) {
inp_map[sty + j][stx + k] = 0;
}
}
}
for (int i = 0; i < M; i++) {
for (int j = 0; j < N; j++) {
if (inp_map[i][j] && !visited[i][j]) {
result.push_back(dfs(i, j, 1));
}
}
}
cout << result.size() << '\n';
sort(result.begin(), result.end());
for (int i : result) {
cout << i << ' ';
}
}풀이 흐름
M,N,K를 입력받는다.- 전체 종이를 1로 초기화한다.
- 직사각형이 차지하는 부분은 0으로 바꾼다.
- 전체 배열을 순회하면서 아직 방문하지 않은 1인 칸을 찾는다.
- 해당 칸에서 DFS를 시작한다.
- DFS를 통해 연결된 영역 전체를 방문 처리하면서 크기를 계산한다.
- DFS가 끝나면 해당 영역의 넓이를
result에 저장한다. - 모든 칸을 확인한 뒤 영역 개수를 출력하고, 넓이들을 정렬해서 출력한다.
구현 포인트
1. 먼저 전체를 1로 두고, 직사각형 부분만 0으로 바꾸기
이 문제는 직사각형 내부를 제외한 나머지 영역을 구하는 문제이기 때문에,
처음부터 전체 종이를 1로 두고 직사각형 부분만 0으로 바꾸는 방식으로 접근했습니다.
for (int i = 0; i < M; i++) {
inp_map.push_back(vector<int>(N, 0));
visited.push_back(vector<int>(N, 0));
for (int j = 0; j < N; j++) {
inp_map[i][j] = 1;
visited[i][j] = 0;
}
}그리고 직사각형 좌표가 주어지면 그 부분을 0으로 채웠습니다.
for (int j = 0; j < edy - sty; j++) {
for (int k = 0; k < edx - stx; k++) {
inp_map[sty + j][stx + k] = 0;
}
}2. 연결된 컴포넌트 개수와 넓이를 동시에 구하기
이 문제는 영역 개수만 필요한 것이 아니라, 각 영역의 크기도 구해야 합니다.
그래서 DFS를 단순 void로 두지 않고 int를 반환하도록 만들었습니다.
int dfs(int y, int x, int size)한 칸 방문할 때마다 size + 1을 넘겨주고,
마지막에 최종 크기를 반환하도록 했습니다.
size = dfs(ny, nx, size + 1);이렇게 해서 하나의 DFS가 끝났을 때 그 연결된 영역의 넓이를 바로 얻을 수 있습니다.
3. 방문하지 않은 1에서만 DFS 시작
전체 배열을 돌면서
- 값이 1이고
- 아직 방문하지 않은 칸
을 만나면 새로운 영역이 시작되는 지점입니다.
if (inp_map[i][j] && !visited[i][j]) {
result.push_back(dfs(i, j, 1));
}이렇게 DFS를 한 번 시작할 때마다 새로운 컴포넌트를 하나 찾은 것이고,
그 반환값이 해당 컴포넌트의 크기가 됩니다.
4. 마지막에는 넓이를 정렬해서 출력
문제에서는 각 영역의 넓이를 오름차순으로 출력해야 하므로,
DFS 결과를 result에 모아둔 뒤 정렬했습니다.
sort(result.begin(), result.end());그리고 영역 개수는 result.size()로 바로 구할 수 있습니다.
cout << result.size() << '\n';