백준 2583 영역 구하기

문제 링크 : https://www.acmicpc.net/problem/2583

※선행해야 할 알고리즘 : BFS/DFS

Algorithm 요약 : M*N 직사각형에서 영역을 만든 직사각형 외의 영역 크기를 출력하시오.

1. 입력 예제를 통해 예를 본다면,

5 7 3

0 2 4 4

1 1 2 5

4 0 6 2

직사각형 공간 내에서

1) [2][0]부터 [3][3]까지

2) [1][1]부터 [4][1]까지

3) [0][4]부터 [1][5]까지

총 세 가지의 또다른 직사각형 영역을 띄게 된다. 

(여기서 후자의 영역을 -1을 한 이유는 칸을 기준으로 좌표가 작성된 것이 아니고, 도형의 선을 기준으로 좌표가 작성되어 후자의 영역은 -1하여 계산하였다.)

즉, 이 영역들은 0으로 초기화 된 M*N 직사각형에서 위의 좌표값만큼이 1로 바뀌는 것이다.

0 0 0 0 1 1 0

0 1 0 0 1 1 0

1 1 1 1 0 0 0

1 1 1 1 0 0 0

0 1 0 0 0 0 0

따라서, 입력받은 좌표에 따라 0으로 초기화 된 M*N 그래프에서 1로 먼저 바꾸어 준다. 

2. 바꾸어 준 vector에서 0인 부분을 통해 BFS를 진행한 알고리즘은 다음과 같다.

//kuklife.tistoty.com #include<iostream> #include<vector> #include<algorithm> #include<queue> using namespace std; typedef vector<vector<int>> d_v; //double vector int dx[] = {1,-1,0,0}; int dy[] = {0,0,1,-1}; int M, N, K; pair<int, int> search_zero(d_v v) { for (int i = 0; i < v.size(); i++) for (int j = 0; j < v[i].size(); j++) if (!v[i][j]) return { i, j }; return { -1, -1 }; } vector<int> sol(d_v v) { vector<int> result; while (1) { queue<pair<int, int>> q; auto s = search_zero(v); if (s.first == -1 && s.second == -1) break; else q.push(s); int count = 1; while (!q.empty()) { int y = q.front().first; int x = q.front().second; v[y][x] = 2; q.pop(); for (int i = 0; i < 4; i++) { int n_y = y + dy[i]; int n_x = x + dx[i]; if (n_y >= 0 && n_y < M && n_x >= 0 && n_x < N && !v[n_y][n_x]) { v[n_y][n_x] = 2; q.push({ n_y, n_x }); count++; } } } result.push_back(count); } return result; } int main() { cin >> M >> N >> K; d_v v(M); //vector 초기화 for (int i = 0; i < M; i++) v[i].resize(N,0); for (int k = 0; k < K; k++) { int start_x, start_y; int finish_x, finish_y; cin >> start_x >> start_y >> finish_x >> finish_y; for (int i = start_x; i < finish_x; i++) for (int j = start_y; j < finish_y; j++) v[j][i] = 1; } auto result = sol(v); sort(result.begin(), result.end()); cout << result.size() << endl; for (int i = 0; i < result.size(); i++) cout << result[i] << " "; return 0; }