[BOJ] 2583. 영역 구하기 - C++

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

 

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

int board[102][102];
int vis[102][102];

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

int m, n, k;

int main() {

	vector<int> countScore;
	queue<pair<int, int>> Q;
	cin >> m >> n >> k;
	int area = 0;

	for (int i = 0; i < n; i++) {
		fill(board[i], board[i] + n, 1);
	}

	for (int i = 0; i < k; i++) {
		int x1, y1, x2, y2;
		cin >> x1 >> y1 >> x2 >> y2;
		
		for (int j = y1; j < y2; j++) {
			fill(board[j] + x1, board[j] + x2, 2);
		}
	}
	

	int count;
	for (int i = 0; i < m; i++) {
		for (int j = 0; j < n; j++) {
			count = 0;
			if (board[i][j] == 1 && !vis[i][j]) {
				vis[i][j] = 1;
				Q.push({ i,j });
				area++; // 영역 시작
				count++; // 첫 지점 count 넣기
			}

			while (!Q.empty()) {

				pair<int, int> cur = Q.front();
				Q.pop();
				
				for (int dir = 0; dir < 4; dir++) {
					int nx = cur.first + dx[dir];
					int ny = cur.second + dy[dir];

					if (nx < 0 || nx >= m || ny < 0 || ny >= n) 
						continue;
					if (board[nx][ny] != 1 || vis[nx][ny]) 
						continue;
					vis[nx][ny] = 1;
					Q.push({ nx,ny });
					count++;
				}
			}
			
			if (count == 0)continue;
			countScore.push_back(count);
		}
		
	}
	cout << area << endl;
	sort(countScore.begin(), countScore.end());


	for (int i = 0; i < countScore.size(); i++) {
		cout << countScore[i] << ' ';
	}
}

 

# 주의할점 

기본 board(범위)는 0으로 전역변수에 초기화 된 상태고

모눈종이에 눈금과 눈금이 아닌 부분을 구분을 해야한다.

그리고 눈금이 표시된 영역이 아닌

눈금이 표시 되지 않은 영역을 찾는 것이다.

 

board를 m과 n 크기만 큼 먼저 1로 채운다 (빈 부분)

 

눈금 부분을 2로 채운다 (테스트 케이스 수 만큼) 입력을 받음

채울 때는 아래와 같이 y값을 for문으로 돌리고 x1부터 x2(열 만큼) 2로 초기화 해준다.

2를 눈금으로 보는거다.

	for (int i = 0; i < k; i++) {
		int x1, y1, x2, y2;
		cin >> x1 >> y1 >> x2 >> y2;
		
		for (int j = y1; j < y2; j++) {
			fill(board[j] + x1, board[j] + x2, 2);
		}
	}

그리고 눈금이 아닌 부분의 영역을 찾는 것이니

board[nx][ny] 가 1인 부분을 bfs로 돌려준다

 

# 고려해야 되는 부분

[수정 전] 

자꾸 이 부분에서 문제가 생겼는데 

방문 여부를 체크 안하고 큐에  push한게 문제였다. 

시작지점에도 반드시 방문여부를 체크해야한다.

			if (board[i][j] == 1 && !vis[i][j]) {
				Q.push({ i,j });
				area++; // 영역 시작
				count++; // 첫 지점 count 넣기
			}

 

[수정 후]

			if (board[i][j] == 1 && !vis[i][j]) {
				vis[i][j] = 1;
				Q.push({ i,j });
				area++; // 영역 시작
				count++; // 첫 지점 count 넣기
			}

 

 

bfs를 돌리는 부분에서 넓이를 세고

시작지점을 찾는 부분에서 area 값을 올려주면

원하는 값을 찾을 수 있다.

 

각 영역의 넓이는 오름차순으로 출력하라고 하여 벡터를 사용해서 정렬했다.

 

 # 개선할 점

문제를 다 풀고 다른 사람의 코드를 봤는데

	for (int j = y1; j < y2; j++) {
			fill(board[j] + x1, board[j] + x2, 2);
		}

이부분을 그냥 1로 초기화 시키고 1이 아닌 부분만 체크해도 될 것 같다.

어차피 for문에서 m과 n이 넘어가면 넓이와 영역을 카운팅 안하니까

2로 초기한 것은

우리가 0인 부분의 넓이를 체크하니까 괜히 m과 n의 영역을 넘어선 곳에서 넓이 체크를 하는게 아닌가 싶어서 

2로 초기화 시켰는데 그럴 필요가 없었다.

 

# 개선한 코드

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

int board[102][102];
int vis[102][102];

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

int m, n, k;

int main() {

	vector<int> countScore;
	queue<pair<int, int>> Q;
	cin >> m >> n >> k;
	int area = 0;


	for (int i = 0; i < k; i++) {
		int x1, y1, x2, y2;
		cin >> x1 >> y1 >> x2 >> y2;
		
		for (int j = y1; j < y2; j++) {
			fill(board[j] + x1, board[j] + x2, 1);
		}
	}
	

	int count;
	for (int i = 0; i < m; i++) {
		for (int j = 0; j < n; j++) {
			count = 0;
			if (board[i][j] == 1 || vis[i][j] ==1 ) continue;
			vis[i][j] = 1;
			Q.push({ i,j });
			area++; // 영역 시작
			count++; // 첫 지점 count 넣기
			while (!Q.empty()) {

				pair<int, int> cur = Q.front();
				Q.pop();
				
				for (int dir = 0; dir < 4; dir++) {
					int nx = cur.first + dx[dir];
					int ny = cur.second + dy[dir];

					if (nx < 0 || nx >= m || ny < 0 || ny >= n) 
						continue;
					if (board[nx][ny] == 1 || vis[nx][ny]) 
						continue;
					vis[nx][ny] = 1;
					Q.push({ nx,ny });
					count++;
				}
			}
			
			//cout << count << ' ';
			countScore.push_back(count);
		}
		
	}
	cout << area << endl;
	sort(countScore.begin(), countScore.end());


	for (int i = 0; i < countScore.size(); i++) {
		cout << countScore[i] << ' ';
	}
}

또, 시작지점을 Q에 넣을 때 board가 1이거나 방문했다면 건너 뛰는 방법으로

CountScore에 0이 push되지 않게 수정하였다.