백준(BOJ) 2583번: 영역 구하기

문제링크:  https://www.acmicpc.net/problem/2583

2583번: 영역 구하기

 

입력 : 첫째 줄에 M과 N, 그리고 K가 빈칸을 사이에 두고 차례로 주어진다. M, N, K는 모두 100 이하의 자연수이다. 둘째 줄부터 K개의 줄에는 한 줄에 하나씩 직사각형의 왼쪽 아래 꼭짓점의 x, y좌표값과 오른쪽 위 꼭짓점의 x, y좌표값이 빈칸을 사이에 두고 차례로 주어진다. 모눈종이의 왼쪽 아래 꼭짓점의 좌표는 (0,0)이고, 오른쪽 위 꼭짓점의 좌표는(N,M)이다. 입력되는 K개의 직사각형들이 모눈종이 전체를 채우는 경우는 없다.

 

출력: 첫째 줄에 분리되어 나누어지는 영역의 개수를 출력한다. 둘째 줄에는 각 영역의 넓이를 오름차순으로 정렬하여 빈칸을 사이에 두고 출력한다.

 

나의 풀이:

각 구역을 나눠서 깊이 우선 탐색을 진행하게 코드를 짰다

 

주의할점? 

그림은 왼쪽 아래 시작이나 만든 모양은 위아래가 뒤집어 놓은 모양이 된다. 허나 문제를 푸는데

에는 지장이 없었다.

또 구역의 수를 지정하는 cnt를 0으로 초기화 해줌으로서 각 구역을 셀 수 있게 해줬다.

 

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int MAX = 100;
int N, M, K;
bool square[MAX][MAX];
bool visited[MAX][MAX];
vector<int> vfind;

const int dy[4] = { 1,-1,0,0 };
const int dx[4] = { 0,0,-1,1 };
int cnt = 0;
void findtheNum(int y, int x)
{
cnt++;
visited[y][x] = true;
for (int next = 0; next < 4; ++next)
{
int ny = y + dy[next];
int nx = x + dx[next];

if (ny >= 0 && nx >= 0 && ny < N && nx < M) {
if (visited[ny][nx] == false && square[ny][nx] == 0)
{
findtheNum(ny, nx);
}
}

}
}
int main()
{
cin >> N >> M >> K;

for (int i = 0; i < K; ++i)
{
int s1, s2, f1, f2;
cin >> s1 >> s2 >> f1 >> f2;
for (int x = s1; x < f1; ++x)
for (int y = s2; y < f2; ++y)
{
square[y][x] = true;
}
}
for (int i = 0; i < N; ++i)
for (int j = 0; j < M; ++j)
if (square[i][j] == 0 && visited[i][j] == 0) {
cnt = 0;
findtheNum(i, j);
vfind.push_back(cnt);
}


sort(vfind.begin(), vfind.end()); 

cout << vfind.size() << endl;  // 3개 구역의 cnt를 vfind에 넣었으니 3이 출력

for (int i = 0; i < vfind.size(); ++i)
cout << vfind[i] << " ";   // 오름차순 정렬된 vfind 배열을 출력

return 0;
}