[DFS,BFS] 백준 2583 영역구하기 C++

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

2583번: 영역 구하기

---

문제 : 

---

풀이 : 

bfs 문제 중에 그림(백준 1926) 문제와 유사해서 그걸 풀었던 방식과 비슷하게 풀었다.

 좌표의 최대값(100)크기의 이차원 배열을 만들어서 색칠된 부분을 1 색칠이 안된 부분을 0으로 두고 bfs 탐색을 통해 0인 부분의 넓이를 구하는 방법이다. 이런 식으로 구해진 넓이는 우선순위 큐에 넣어서 오름차순으로 정렬하여 출력가능

단, 조금 주의해야 할 점이 있다면 입력될 때 색칠된 직사각형의 왼쪽아래 꼭짓점 좌표와 오른쪽 위의 꼭짓점 좌표가 주어 진다 이 좌표를 이용해서 초기 square 배열을 세팅하는 과정이 어려웠다 이 과정만 끝나면 그냥 bfs 탐색 이용해 호출된 횟수를 이용하여 영역의 개수와 넓이를 구하면 된다.

 내가 접근한 방법은 우선 두 좌표를 입력받는다. (x1, y1) (x2, y2) 그럼 직사각형의 넓이는 X = x2 - x1, Y = y2 - y1 일 때, 넓이가 XY인 직사각형일 것이다. 이를 이중 반복문 이용해서 채워하는데 시작점이 어디 부터 설정해야 할지가 어려웠다. 일반적인 배열 반복문 사용하는 방법대로 하기 위해 사각형을 오른쪽으로 회전시킨다고 생각하고 문제를 풀었다. 무슨 말이냐면 (0, 2) , (4, 4) 좌표가 주어졌을 때 가로 2 세로 4인 사각형으로 생각하면 일반적으로 사용하는 이중반복문과 순서가 같아 채워넣기 쉽다. 

왼쪽아래 좌표
	오른쪽 위 좌표

이런식으로 문제에 나와있는 예제를 채우면

0	0	1	1	0
0	1	1	1	1
0	0	1	1	0
0	0	1	1	0
1	1	0	0	0
1	1	0	0	0
0	0	0	0	0

이렇게 생각하고 좌표가 0이고 방문하지 않은 좌표를 시작점으로 bfs 탐색을 진행하면 되고 이때 진행되는 bfs함수의 수가 영역의 수 이고 bfs 탐색을 진행하면 while문이 몇번 돌아가는지 체크하면 영역의 넓이를 구할 수 있다

 

code :

#include <iostream>
#include <queue>
#define MAX 102

using namespace std;

int m, n, k;
int square[MAX][MAX];
int vis[MAX][MAX];

queue<pair<int, int>> que;
priority_queue<int,vector<int>,greater<int>> sizeque;
int dx[4] = { 1,0,-1,0 };
int dy[4] = { 0,1,0,-1 }; // 상하좌우 네 방향을 의미

int cnt = 0;
int sqSize = 0;

void bfs(int y, int x) {
	que.push({ y,x });
	vis[y][x] = 1;
	while (!que.empty()) {
		sqSize++;
		auto cur = que.front();
		que.pop();

		for (int i = 0; i < 4; i++) {
			int nx = cur.first + dx[i];
			int ny = cur.second + dy[i];
			if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue; // 범위 밖일 경우 넘어감
			if (vis[nx][ny] || square[nx][ny] != 0) continue;
			vis[nx][ny] = 1; 
			que.push({ nx,ny });
		}
	}
	sizeque.push(sqSize);
	sqSize = 0;
}
int main() {
	cin >> m >> n >> k;
	int x1, y1, x2, y2;
	for(int i = 0; i <k;i++){
		cin >> x1 >> y1 >> x2 >> y2;
		int X = x2 - x1;
		int Y = y2 - y1;
		for (int j = 0; j < X; j++) {
			for (int k = 0; k < Y; k++) {
				square[j+x1][k+y1] = 1;
				
			}
		}

	}

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (vis[i][j] == 1 || square[i][j] == 1) continue;
			cnt++;
			bfs(i, j);
		}
	}

	cout << cnt << endl;
	while (!sizeque.empty()) {
		cout << sizeque.top() << " ";
		sizeque.pop();
	}
	
	


}