[C++] 백준(BOJ) - 2583 : 영역 구하기
인프런에 있는 큰돌님의 강의 10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트를 듣고 정리한 필기입니다.
문제
눈금의 간격이 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개의 직사각형 내부를 제외한 나머지 부분이 몇 개의 분리된 영역으로 나누어지는지, 그리고 분리된 각 영역의 넓이가 얼마인지를 구하여 이를 출력하는 프로그램을 작성하시오.
알고리즘
- 그래프 이론
- 그래프 탐색
- 깊이 우선 탐색 (DFS)
- int 형 DFS
- Connected Component
풀이
- int형 DFS를 활용한 Composite Component
- 네 방향 탐색을 위한 y, x 배열 미리 만들기 (문제에서 주어진 n, m에 따라 가로 세로 방향 잘 잡기)
- 탐색에서 제외할 직사각형을 미리 만들어진 배열에 담기
- DFS 탐색을 이용해 분리된 영역의 넓이를 더해 나가고 이를 미리 만들어 둔 vector에 담는다 (Connected Component - DFS 탐색)
- sort 함수를 이용해 오름차순 정렬한다
코드
// BOJ - 2583 : 영역 구하기
#include <bits/stdc++.h>
using namespace std;
const int INF = -2147000000;
const int dy[] = { -1, 0, 1, 0 };
const int dx[] = { 0, 1, 0, -1 };
int m, n, k;
int a[104][104], visited[104][104];
vector<int> v;
int dfs(int y, int x)
{
int res = 1; // 정점 하나의 가치는 1 (넓이)
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 >= n || nx >= m) continue;
if (a[ny][nx] != 1 && !visited[ny][nx]) // 직사각형이 그려져있지 않고, 방문한적이 없다면
{
res += dfs(ny, nx); // 분리된 영역의 넓이에 더해 나가기
}
}
return res;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> m >> n >> k;
for (int l = 0; l < k; l++)
{
int sx, sy, ex, ey;
cin >> sx >> sy >> ex >> ey;
for (int i = sx; i < ex; i++)
{
for (int j = sy; j < ey; j++)
{
a[i][j] = 1;
}
}
}
for (int i = 0; i < n; i++)
{
for (int j = 0; j < m; j++)
{
if (a[i][j] != 1 && !visited[i][j])
{
v.push_back(dfs(i, j));
}
}
}
cout << v.size() << '\n';
sort(v.begin(), v.end());
for (auto i : v) cout << i << ' ';
return 0;
}
평가
- int형 DFS를 이용한 Connected Composite 문제
- 정점의 가치를 1로 두고 마치 직사각형의 넓이를 가지는 것과 같이 생각한다
- 문제에서 주어진 m, n을 탐색하기 쉽게 90도 혹은 180도 회전시켜 탐색을 용이하게 생각한다
- void, int형 반환 타입에 따라 자유롭게 함수를 구상할 수 있는 능력을 기른다
