알고리즘 :: 백준 :: 2583 - 영역 구하기

 

 

 

❔문제

🔗문제링크

 

🔄 문제 및 입출력 조건 파악

의도적으로 좌표 햇갈리게 만든 문제입니다.
만일 평소 자신에게 익숙한 좌표계나 문자(N, M, x, y)가 아니라면 주의해서 문제를 읽도록 합시다.

1. 세로가 M, 가로가 N (M, N ≤100)
2. K개의 직사각형 좌표 왼쪽 아래 꼭짓점 (x, y), 오른쪽 위 꼭짓점 (x, y)
3. 모눈종이의 왼쪽 아래 꼭짓점의 좌표가 (0,0)이고, 오른쪽 위 꼭짓점의 좌표는(N,M)이다.
   • 이거 때문에 햇갈릴 필요 없습니다.
   • 만일 자신에게 편한 좌표계가 왼쪽 위 꼭짓점이 (0, 0), 오른쪽 아래 꼭짓점이 (M, N) 이라면 그냥 원래대로 두고 풀어도 영역의 넓이가 달라지진 않기 때문입니다. 그냥 그림이 거울대칭으로 뒤집혔다고 생각하면 됩니다.

✏️ 문제풀이

윗 절에서 언급했듯, 햇갈리는 좌표계 표현법만 극복한다면 이 문제 역시 connected component 문제입니다.

(0, 0) 부터 (N, M)까지 순회 → 아직 방문하지 않은 빈칸을 발견 → 해당 점을 시작점으로 해서 DFS 또는 BFS를 한 번 돌리면 됩니다.

 

모든 칸을 순회하고 나서, DFS 또는 BFS를 몇 번 호출했는지가 영역의 넓이입니다.

이 문제는 영역의 개수와 함께 영역의 넓이를 오름차순으로 나타내야하므로
구한 영역의 넓이는 `std::vector<int>`에 넣어주고, 출력하기 전에 `sort()`로 정렬해주도록 합시다.

 

📝 코드

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

// Be careful with position x, y.
// This question make confuse intentionally.

constexpr int dy[] = {-1, 0, 1, 0};
constexpr int dx[] = {0, 1, 0, -1};

int M, N, K;		// M = row, N = col in this question.
array<array<bool, 101>, 101> arr, visited;

inline bool isNotValid(int y, int x) {
	return (y < 0) || (x < 0) || (y >= M) || (x >= N);
}

int dfs(int y, int x) {
	visited[y][x] = true;
	int ret = 1;
	for (int i = 0; i < 4; ++i) {
		int ny = y + dy[i], nx = x + dx[i];
		if (isNotValid(ny, nx) || visited[ny][nx] || arr[ny][nx]) continue;
		ret += dfs(ny, nx);
	}
	return ret;
}

int main() {
	ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
	
	cin >> M >> N >> K;
	while (K--) {
		int sx, sy, ex, ey;
		cin >> sx >> sy >> ex >> ey;
		for (int y = sy; y < ey; ++y)
			for (int x = sx; x < ex; ++x)
				arr[y][x] = true;
	}
	vector<int> ret;
	for (int y = 0; y < M; ++y)
		for (int x = 0; x < N; ++x)
			if (!visited[y][x] && !arr[y][x])
				ret.push_back(dfs(y, x));
	
	cout << ret.size() << '\n';
	sort(begin(ret), end(ret));
	for (int i : ret) cout << i << ' ';
}

 

🔗 코드 링크

🕧 결과