백준 2583_영역 구하기 문제풀이 in C++

in Devlog on Algorithm
  1. 문제 URL
  2. 문제 요구사항
  3. 접근 방법
  4. 풀이 순서
  5. 소스코드
  6. 문제 풀이 결과

문제 URL

https://www.acmicpc.net/problem/2583

문제 요구사항

  • 눈금의 간격이 1인 M×N(M,N≤100)크기의 모눈종이가 있다.
  • 이 모눈종이 위에 눈금에 맞추어 K개의 직사각형을 그릴 때, 이들 K개의 직사각형의 내부를 제외한 나머지 부분이 몇 개의 분리된 영역으로 나누어진다.

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

접근 방법

  • 주의해야할 것은 맵의 좌측 아래가 (0,0) 맵의 우측 위가 (M, N) 이라는 것, K의 개수는 제한이 없다는 것이다. 이를 생각하고 코딩하게 되면 K 범위만큼 map에 값을 채우고, 남은 영역들을 bfs 탐색하면 된다.

풀이 순서

  1. M, N, K를 입력받고, K의 크기만큼 각 직사각형들의 좌표들을 left_bottom ( vector ) , right_top ( vector ) 변수에 저장한다.
  2. 입력 받은 K개의 직사각형 좌표를 이용해서 map ( int 2차원 배열 )에 직사각형 부분에는 1을 넣는다. 이 때, 해당 부분에 visited ( bool 2차원 배열 ) 도 true로 하여 해당 부분은 탐색하지 못하도록 한다.
  3. 준비된 map과 visted를 이중 for문을 이용하여 bfs 탐색을 한다. 이 때, area는 영역의 개수, area_cnt ( int vector )는 해당 영역의 넓이를 갖게 된다.
  4. sort함수를 이용하여 area_cnt를 오름차순 정렬한다.
  5. 문제 출력 형식에 맞게 area와 area_cnt를 출력한다.

소스코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>

using namespace std;

int map[100][100] = { 0, };
bool visited[100][100] = { false, };
vector<pair<int, int>> left_bottom;
vector<pair<int, int>> right_top;
int M, N, K;
int dx[] = { 0, 1, 0, -1 };
int dy[] = { 1, 0, -1, 0 };
int area = 0;
vector<int> area_cnt;
void input() {
	cin >> M >> N >> K;

	for (int i = 0; i < K; i++) {
		int leftX, leftY, rightX, rightY;
		cin >> leftX >> leftY >> rightX >> rightY;

		left_bottom.push_back({ leftX, leftY });
		right_top.push_back({ rightX, rightY });
	}
}

void setMap() {
	for (int i = 0; i < K; i++) {
		int leftX = left_bottom[i].first, leftY = left_bottom[i].second, rightX = right_top[i].first, rightY = right_top[i].second;

		for (int row = leftY; row < rightY; row++) {
			for (int col = leftX; col < rightX; col++) {
				map[row][col] = 1;
				visited[row][col] = true;
			}
		}
	}
}

int bfs(int x, int y) {
	int res_cnt = 0;
	queue<pair<int, int>> q;

	q.push({ x, y });
	visited[x][y] = true;

	while (!q.empty()) {
		int xx = q.front().first;
		int yy = q.front().second;

		q.pop();

		res_cnt++;

		for (int i = 0; i < 4; i++) {
			int nx = xx + dx[i];
			int ny = yy + dy[i];

			if (nx >= 0 && ny >= 0 && nx < M && ny < N) {
				if (visited[nx][ny] == false) {
					q.push({ nx, ny });
					visited[nx][ny] = true;
				}
			}
		}
	}

	return res_cnt;
}

void solution() {
	setMap();

	for (int i = 0; i < M; i++) {
		for (int j = 0; j < N; j++) {
			if (visited[i][j] == false) {
				area++;
				area_cnt.push_back(bfs(i, j));
			}
		}
	}

	sort(area_cnt.begin(), area_cnt.end());
}

void output() {
	cout << area << "\n";
	for (int i = 0; i < area; i++) {
		cout << area_cnt[i] << " ";
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	input();
	solution();
	output();

	return 0;

문제 풀이 결과