백준 2583 문제풀이
in Computer Science on Algorithm
문제 링크
ㅋhttps://www.acmicpc.net/problem/2583
문제 설명
눈금의 간격이 1인 M×N(M,N≤100)크기의 모눈종이가 있다. 이 모눈종이 위에 눈금에 맞추어 K개의 직사각형을 그릴 때, 이들 K개의 직사각형의 내부를 제외한 나머지 부분이 몇 개의 분리된 영역으로 나누어진다. 예를 들어 M=5, N=7 인 모눈종이 위에 <그림 1>과 같이 직사각형 3개를 그렸다면, 그 나머지 영역은 <그림 2>와 같이 3개의 분리된 영역으로 나누어지게 된다. <그림 2>와 같이 분리된 세 영역의 넓이는 각각 1, 7, 13이 된다. M, N과 K 그리고 K개의 직사각형의 좌표가 주어질 때, K개의 직사각형 내부를 제외한 나머지 부분이 몇 개의 분리된 영역으로 나누어지는지, 그리고 분리된 각 영역의 넓이가 얼마인지를 구하여 이를 출력하는 프로그램을 작성하시오.
문제 분석
문제에서 주어진 K개의 직사각형이 겹치는 부분을 처리할 때, 색칠된 부분(직사각형 내부)은 방문하지 않고, 나머지 영역(겹치지 않는 부분)을 탐색하여 분리된 영역(컴포넌트)을 구하는 방식으로 해결할 수 있다. 문제를 보자마자 DFS로 탐색하면 된다고 생각했다.
코드
#include <bits/stdc++.h>
using namespace std;
int m, n, k;
#define y1 aaaa
int x1, x2, y2, y1;
int a[104][104], visited[104][104];
int dy[4] = {-1, 0, 1, 0};
int dx[4] = {0, 1, 0, -1};
vector<int> ret;
int dfs(int y, int x) {
visited[y][x] = 1;
int count = 1;
for (int i = 0; i < 4; i++) {
int ny = y + dy[i];
int nx = x + dx[i];
if (ny < 0 || nx < 0 || nx >= n || ny >= m) {
continue;
}
if (visited[ny][nx] == 1 || a[ny][nx] == 1) {
continue;
}
count += dfs(ny, nx);
}
return count;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin >> m >> n >> k;
memset(a, 0, sizeof(a));
memset(visited, 0, sizeof(visited));
for (int i = 0; i < k; i++) {
cin >> x1 >> y1 >> x2 >> y2;
for (int x = x1; x < x2; x++) {
for (int y = y1; y < y2; y++) {
a[y][x] = 1;
}
}
}
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (a[i][j] != 1 && visited[i][j] == 0) {
ret.push_back(dfs(i, j));
}
}
}
sort(ret.begin(), ret.end());
cout << ret.size() << '\n';
for (auto i : ret) {
cout << i << ' ';
}
return 0;
}
문제는 남은 영역을 탐색하여 몇 개의 분리된 영역이 있는지와 각 영역의 크기를 계산하는 기능을 수행한다. 프로그램은 먼저 M, N, K 값을 입력받고, a 배열을 사용하여 모눈종이를 초기화한다. 이 배열은 각 칸의 색칠 상태를 저장하며, 기본적으로 모든 값을 0으로 설정하여 빈 상태로 초기화한다. 그 후 K개의 직사각형의 좌표를 입력받고, 이 좌표에 해당하는 모눈종이의 부분을 1로 설정하여 색칠된 상태를 나타낸다. 이후 dfs 함수를 통해 남은 영역을 탐색한다. 이 함수는 현재 위치를 방문 처리하고, 네 방향(위, 오른쪽, 아래, 왼쪽)으로 인접한 칸을 재귀적으로 탐색하여 색칠되지 않은 영역의 크기를 계산한다. 만약 탐색하려는 위치가 범위를 벗어나거나 이미 방문했거나 색칠된 칸이면 탐색을 중단하고, 유효한 경우에만 재귀 호출을 통해 연결된 영역의 크기를 계속해서 증가시킨다. 모든 탐색이 끝난 후, 발견된 영역의 크기를 ret 벡터에 저장하고, 이를 정렬한 뒤, 총 영역의 개수와 각 영역의 크기를 출력한다.
문제를 풀면서 알게된 사실은 C++의 #include <bits/stdc++.h> 헤더를 사용할 때, 이 헤더 파일에 이미 y1이라는 변수가 정의되어 있다고 한다. 따라서 이름을 바꿔주어야 했다. 왜 컴파일 에러가 계속 나는가 했다.
Reference
나의 뇌