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개의 직사각형 내부를 제외한 나머지 부분이 몇 개의 분리된 영역으로 나누어지는지,
그리고 분리된 각 영역의 넓이가 얼마인지를 구하여 이를 출력하는 프로그램을 작성하시오.
접근
영역을 탐색하는건 그래프 탐색을 이용하면 간단하고 입력으로 들어온 직사각형의 두 x,y와 좌표를 변환하는게 관건이다.
내가 생각한 방법으로는 좌하단 좌표로 들어온 첫 좌표는 x와 y를 바꾼다음(swap) 행인 M값에서 x를 빼고, 1을 더 뺴주면 최종 x,y로 변환된다.
그리고 우상단 좌표도 일단 x,y를 뒤집고(swap) M에서 x를 빼주고, 이번엔 y에서 1을 뺴준다. 그럼 최종 x,y로 변환된다.
이 두 x1,y1과 x2,y2를 이용해 이중반복문을
i = x2 ~ i <= x1 하나, j = y1 ~ j <= y2로 두개 쓰면 해당 좌표가 나타내는 직사각형의 벡터식 좌표가 나온다.
이 반복문을 통해 직사각형 위치를 bool로 마킹해주고 그래프 탐색을 돌려주면 된다.
문제해결
> 행, 열, 직사각형의 개수를 입력받고 직사각형의 위치를 마킹해줄 paper bool형 벡터를 선언해준다.
> 직사각형의 개수K개 만큼 while문을 돌며 x1, x2와 x2, y2를 입력받고 이를 변환해준다.
> 둘다 x와 y를 뒤집고 M에서 x값을 각각 빼준뒤 첫 좌표는 x에 -1, 두번째 좌표는 y에 -1해준다.
> x2부터 x1과 같거나작을때까지 한, y1부터 y2보다 작거나 같을 때까지 두개로 반복문을 돌며 직사각형을 마킹해준다.
> 이제 M행 N열 크기의 모눈종이를 모두 돌며 마킹이 되어있지 않는 위치를 Paper그래프 탐색 메소드로 탐색한다.
탐색 하며 각각 영역마다 Paper메소드의 값을 리턴받으며 이건 영역의 크기이다.
그리고 이 함수가 돌아갈 때마다 영역의 개수가 늘어난다 이므로 영역의 수도 누적해준다.
> 최종 적으로 영역의 수와, rst에 저장한 영역의 크기들을 오름차순 정렬하고 출력한다.
> Paper 메소드에선 위 모눈종이 탐색 반복문에서 continue에 걸리지 않은 좌표가 입력으로 들어가 이를 사방탐색해주며 탐색한 좌표는 papaer벡터에 마킹을 해 재탐색을 안하게 해준다.코드
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
int M, N, K;
vector<vector<bool>> paper;
int dir[4] = { -1, 1, 0, 0 };
int dic[4] = { 0, 0, -1, 1 };
int Paper(pair<int, int> p)
{
queue<pair<int, int>> q;
q.push(p);
int cnt = 0;
while (!q.empty())
{
int fr = q.front().first;
int fc = q.front().second;
q.pop();
if (paper[fr][fc]) continue;
paper[fr][fc] = true;
cnt++;
for (int i = 0; i < 4; i++)
{
int nr = fr + dir[i];
int nc = fc + dic[i];
if (nr < 0 || nr >= M) continue;
if (nc < 0 || nc >= N) continue;
q.push({ nr, nc });
}
}
return cnt;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
cin >> M >> N >> K;
paper.assign(M, vector<bool>(N, false));
while (K--)
{
int x1, y1, x2, y2;
cin >> x1 >> y1 >> x2 >> y2;
swap(x1, y1);
x1 = M - x1 - 1;
swap(x2, y2);
x2 = M - x2;
y2 = y2 - 1;
for (int i = x2; i <= x1; i++)
{
for (int j = y1; j <= y2; j++)
{
paper[i][j] = true;
}
}
}
vector<int> rst;
int rcnt = 0;
for (int i = 0; i < M; i++)
{
for (int j = 0; j < N; j++)
{
if (paper[i][j]) continue;
rst.push_back(Paper({i,j}));
rcnt++;
}
}
sort(rst.begin(), rst.end());
cout << rcnt << '\n';
for (auto& a : rst) cout << a << " ";
}
후기
직사각형 영역을 변환하는 로직을 짜는게 꽤 흥미로웠다.
중간에 q.pop()안해서 무한루프 났는데 알아채지 못했다. 기본적인걸 놓치지 말자
