영역 구하기 (feat. 백준, 2583번)

영역 구하기
https://www.acmicpc.net/problem/2583

2583번: 영역 구하기

 

반응형

 

// woohyeon.kim
// kim519620.tistory.com
#include <iostream>
#include <string.h>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;
int M, N, K, dx[4], dy[4], arr[101][101];
bool visit[101][101];
vector<int> ans;
void bfs(register int x, register int y) {
	register int count = 1;
	queue<pair<int, int>> q;
	q.push(make_pair(x, y));
	visit[x][y] = true;
	while (!q.empty()) {
		auto p = q.front(); q.pop();
		x = p.first, y = p.second;
		for (register int d = 0, nx, ny; d < 4; ++d) {
			nx = x + dx[d], ny = y + dy[d];
			if (0 <= nx && nx < M && 0 <= ny && ny < N && !visit[nx][ny] && arr[nx][ny] == 0)
				visit[nx][ny] = true, q.push(make_pair(nx, ny)), ++count;
		}
	}
	ans.push_back(count);
}
int main() {
	ios::sync_with_stdio(false), cin.tie(NULL);
	dx[0] = 1, dx[1] = -1, dx[2] = dx[3] = 0;
	dy[0] = dy[1] = 0, dy[2] = 1, dy[3] = -1;
	memset(arr, 0, sizeof(arr));
	memset(visit, false, sizeof(visit));
	cin >> M >> N >> K;
	for (register int k = 0, x1, y1, x2, y2; k < K; ++k) {
		cin >> y1 >> x1 >> y2 >> x2;
		for (register int x = x1, y; x < x2; ++x)
			for (y = y1; y < y2; ++y)
				arr[x][y] = 1;
	}
	for (register int x = 0, y; x < M; ++x)
		for (y = 0; y < N; ++y)
			if (!visit[x][y] && arr[x][y] == 0)
				bfs(x, y);
	cout << ans.size() << "\n";
	sort(ans.begin(), ans.end());
	for (auto& v : ans)
		cout << v << " ";
	return 0;
}
// *&)*@*

 

1. 문제로 입력된 영역을 1로 채워줍니다.
2. (0,0)부터 시작하여 인접한 곳이 0이고 방문한 적이 없는 곳으로 bfs 탐색을 진행합니다. bfs가 종료되면 탐색 횟수를 자료구조 vector에 저장합니다.
3. (M,N)까지 탐색이 완료되면 자료구조 vector의 크기와 오름차순으로 정렬된 값을 출력합니다.