[BOJ] C++ 2583 "영역 구하기" 문제 풀이 _ nov

#INFO

난이도 : SILVER1

문제 유형 : BFS

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

2583번: 영역 구하기

---

#SOLVE

문제의 조건에 의하면 M X N 크기의 모눈종이에 K개의 직사각형의 좌측 하단 좌표와 우측 상단 좌표가 주어진다. 

이때 K개의 직사각형이 만들어지는 곳을 이동 불가능한 공간 (1) 로 초기화 시키고 나머지 빈 부분 (0) 에 대해서 BFS 알고리즘을 적용시키는 방식으로 풀이했다.

int board[101][101] : 영역의 정보를 저장할 배열 (0 : 이동가능 1 : 이동 불가능)

isVisited[101][10] : 영역의 방문 여부를 저장할 배열

int dx[4], dy[4] : 상하좌우 이동을 도와줄 변수

 

우선, 가로(m) 세로(n) 직사각형의 개수(k)를 입력받은 후 k개의 직사각형이 만들어지는 공간의 배열값을 1(이동불가)로 초기화한다.

	int m, n, k;
	cin >> m >> n >> k;
	while(k--){
		int x, y, xx, yy;
		cin >> x >> y >> xx >> yy;
		for(int i = y; i < yy; i++){
			for(int j = x; j < xx; j++){
				board[i][j] = 1;
			} 
		}
	}

 

주어진 좌표를 이용해 이동불가 공간을 잘 설정했다면, BFS 알고리즘을 적용 시키기만 하면 쉽게 해결된다.  count 변수에는 영역의 개수가 저장되고 ans 벡터는 각 영역의 넓이가 저장된다.

	int count = 0; // 영역의 개수
	vector<int> ans; // 각 영역의 넓이
	queue<pair<int,int>> Q;
	for(int i = 0; i < m; i++){
		for(int j = 0; j < n; j++){
			if(board[i][j] == 1 || isVisited[i][j]) continue;
			count++;
			Q.push({i, j});
			isVisited[i][j] = 1;
			int width = 1;
			while(!Q.empty()){
				auto cur = Q.front();
				Q.pop();
				for(int dir = 0; dir < 4; dir++){
					int nx = cur.X + dx[dir];
					int ny = cur.Y + dy[dir];
					if(nx < 0 || nx >= m || ny < 0 || ny >= n) continue;
					if(isVisited[nx][ny] || board[nx][ny] == 1) continue;
					Q.push({nx, ny});
					isVisited[nx][ny] = 1;
					width++;
				}
			}
			ans.push_back(width);
		}
	}

 

sort 함수를 이용해 ans 벡터를 오름차 정렬한 후 출력해 주면 된다.

	cout << count << '\n';
	sort(ans.begin(), ans.end());
	for(int i : ans) {
		cout << i << " ";
	}

---

#CODE

#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second
int board[101][101];
bool isVisited[101][101];
int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, 1, 0, -1};

int main(int argc, char* argv[]) {
	ios::sync_with_stdio(0);
	cin.tie(0);
	int m, n, k;
	cin >> m >> n >> k;
	while(k--){
		int x, y, xx, yy;
		cin >> x >> y >> xx >> yy;
		for(int i = y; i < yy; i++){
			for(int j = x; j < xx; j++){
				board[i][j] = 1;
			} 
		}
	}
	
	int count = 0; // 영역의 개수
	vector<int> ans; // 각 영역의 넓이
	queue<pair<int,int>> Q;
	for(int i = 0; i < m; i++){
		for(int j = 0; j < n; j++){
			if(board[i][j] == 1 || isVisited[i][j]) continue;
			count++;
			Q.push({i, j});
			isVisited[i][j] = 1;
			int width = 1;
			while(!Q.empty()){
				auto cur = Q.front();
				Q.pop();
				for(int dir = 0; dir < 4; dir++){
					int nx = cur.X + dx[dir];
					int ny = cur.Y + dy[dir];
					if(nx < 0 || nx >= m || ny < 0 || ny >= n) continue;
					if(isVisited[nx][ny] || board[nx][ny] == 1) continue;
					Q.push({nx, ny});
					isVisited[nx][ny] = 1;
					width++;
				}
			}
			ans.push_back(width);
		}
	}
	
	cout << count << '\n';
	sort(ans.begin(), ans.end());
	for(int i : ans) {
		cout << i << " ";
	}
	return 0;
}