[BOJ] 2583. 영역 구하기 (bfs, dfs, graphs, graph_traversal)

Silver I

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

2583번: 영역 구하기

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

예를 들어 M=5, N=7 인 모눈종이 위에 <그림 1>과 같이 직사각형 3개를 그렸다면, 그 나머지 영역은 <그림 2>와 같이 3개의 분리된 영역으로 나누어지게 된다.

<그림 2>와 같이 분리된 세 영역의 넓이는 각각 1, 7, 13이 된다.

M, N과 K 그리고 K개의 직사각형의 좌표가 주어질 때, K개의 직사각형 내부를 제외한 나머지 부분이 몇 개의 분리된 영역으로 나누어지는지, 그리고 분리된 각 영역의 넓이가 얼마인지를 구하여 이를 출력하는 프로그램을 작성하시오.

 

input:

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

 

output:

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

 

 

---

Idea :

• 나머지 영역의 넓이 구하기 → BFS 이용
  • 현재 지점의 위, 아래, 오른쪽, 왼쪽 중 이동 가능한 모든 지점을 다음 지점으로 함
  • 이동 가능한 모든 지점에 대해 위 동작을 반복
  • 거쳐온(이동했던) 지점의 개수가 영역의 넓이가 됨
  • 주의! 중복을 방지하기 위해 각 칸은 한 번씩만 이동 가능해야 함 
• 나머지 영역의 시작점 구하기
  • 이중 for문을 이용해 모눈 종이의 모든 칸을 체크해보고, 직사각형에 포함되어 있지 않을 경우 나머지 영역의 시작점이 됨
  • 주의! 이전에 구했던 시작점과 한 영역에 있는 나머지 부분을 시작점으로 중복체크하지 않아야 함
    → 이미 넓이를 구한 영역에 대해 체크가 필요

Code :   

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

using namespace std;

struct Point {
	int m, n;
	Point(int _m, int _n) : m(_m), n(_n) {}
};

int M, N, K;

/* get_area: 직사각형에 포함되지 않는 나머지 영역의 넓이를 구하는 함수
 *           BFS를 이용해 이동할 수 있는(직사각형에 포함되지 않은) 모든 지점을 가보고 그 개수를 구함, 지점의 개수 = 넓이
 *
 * parameters - ch: 직사각형에 포함되어 있는지 여부
                (m, n): 영역이 시작되는 point
 * return - (m, n)에서 시작하여 직사각형에 포함되지 않은 영역의 넓이
 */
int get_area(vector<vector<bool>> &ch, int m, int n) {
	int ans = 0;

	queue<Point> Q;
	Q.push(Point(m, n));
	ch[m][n] = true;

	int MM[4] = {-1, 0, 1, 0};
	int NN[4] = {0, 1, 0, -1};
	while (!Q.empty()) {
		Point cur = Q.front(); Q.pop();
		ans++;

		for (int i=0; i<4; i++) {
			int next_m = cur.m + MM[i], next_n = cur.n + NN[i]; 
			if (next_m < 0 || next_m >= M || next_n < 0 || next_n >= N) continue;
			if (ch[next_m][next_n]) continue;
			Q.push(Point(next_m, next_n));
			ch[next_m][next_n] = true;
		}
	}
	return ans;
}

int main() {
	// ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	// freopen("input.txt", "rt", stdin);

	/* input */
	cin >> M >> N >> K;

	vector<vector<bool>> paper(M, vector<bool>(N, false));
	while (K--){
		int n1, m1, n2, m2;
		cin >> n1 >> m1 >> n2 >> m2;
		for (int i = m1; i < m2; i++) {
			for (int j = n1; j < n2; j++)
				paper[i][j] = true;
		}
	}

	/* solve */
	vector<int> ans; // 직사각형에 포함되지 않는 나머지 영역의 넓이, ans의 원소 개수 = 나머지 영역의 개수
	for (int i=0; i<M; i++) {
		for (int j=0; j<N; j++) {
			if (!paper[i][j]) 
				ans.push_back(get_area(paper, i, j));
		}
	}

	sort(ans.begin(), ans.end());
	cout << ans.size() << "\n";
	for (auto e : ans)
		cout << e << " ";
	
}

 

---

Result : 

메모리: 2024 KB,  시간: 0 ms

 

Review :