백준 2583번 - 영역 구하기

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

2583번: 영역 구하기

 

풀이 과정

 꼭짓점 좌표에 따라서 사각형을 맵에 기록하고 최종적으로 mp값이 0인 연결 컴포넌트의 개수와 각 컴포넌트의 크기를 구하는 문제였다. 꼭짓점 좌표를 입력받고 시작 꼭짓점 이상 마지막 꼭짓점 미만으로 mp에 값을 입력했다. dfs()에서 노드 하나를 방문하고 종료되면 cnt++를 수행하며 컴포넌트의 크기를 구했다.

 

느낀 점

 문제에 2가지 포인트가 있었다고 생각한다. 첫 째는 DFS를 구현할 때 리턴값을 활용할 줄 아는가, 둘 째는 꼭짓점이 가지는 의미를 알고 이를 이용해 잘 입력받았는가 이다. 나는 두 번째를 뒤늦게 알아차려 시간이 조금 소요되었다. 꼭짓점과 칸의 인덱스를 매치 해봤을 때, 시작 꼭짓점에 해당하는 좌표의 칸은 직사각형 안에 포함 되지만, 마지막 꼭짓점 좌표에 해당하는 칸은 포함되지 않는다. 따라서 시작 꼭짓점 이상, 종료 꼭짓점 미만으로 사각형 범위를 지정하고 값을 채워나가야 했다. 섬세하게 생각해 볼 수 있는 기회가 됬다.

 

#include<bits/stdc++.h>
using namespace std;

const int MAX = 101;
int n, m, k, cnt;
int mp[MAX][MAX], visited[MAX][MAX];
int my[4] = { 1, 0 , -1, 0 }, mx[4] = { 0, 1, 0, -1 };
vector<int> ret;

int dfs(int y, int x) {
	if (mp[y][x] != 0 || visited[y][x]) return 0;
	visited[y][x] = 1;
	for (int i = 0; i < 4; i++) {
		int ny = my[i] + y;
		int nx = mx[i] + x;
		if (ny < 0 || ny >= n || nx < 0 || nx >= m) continue;
		dfs(ny, nx);
	}
	cnt++;
	return cnt;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	//입력
	cin >> n >> m >> k;
	for (int i = 0; i < k; i++) {
		int fy, fx, ly, lx;
		cin >> fx >> fy >> lx >> ly;
		for (int j = fy; j < ly; j++) {
			for (int z = fx; z < lx; z++) {
				mp[j][z]++;
			}
		}
	}
	
	/* 입력 테스트
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cout << mp[i][j] << " ";
		}
		cout << "\n";
	}
	*/

	//수행
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cnt = 0;
			int temp = dfs(i, j);
			if(temp) ret.push_back(temp);
		}
	}
	//정렬
	sort(ret.begin(), ret.end());
	//출력
	cout << ret.size() << "\n";
	for (int i = 0; i < ret.size(); i++) cout << ret[i] << " ";
	return 0;
}