[백준 2583] 영역 구하기 (C++/Python)

C++)

#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;

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

int main(void) {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);

	int m, n, k;
	cin >> n >> m >> k;

	int x1, y1, x2, y2;
	while (k--) {
		cin >> y1 >> x1 >> y2 >> x2;

		for (int i = x1; i < x2; i++) {
			for (int j = y1; j < y2; j++) {
				arr[i][j] = 1;
			}
		}
	}

	int total = 1;
	vector<int> v;
	queue<pair<int, int>> q;

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {

			if (arr[i][j] == 0 && visited[i][j] == 0) {
				q.push({ i,j });
				visited[i][j] = total;
				int count = 0;

				while (!q.empty()) {
					int x = q.front().first;
					int y = q.front().second;
					q.pop();
					count++;

					for (int k = 0; k < 4; k++) {
						int nx = x + dx[k];
						int ny = y + dy[k];

						if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;

						if (arr[nx][ny] == 0 && visited[nx][ny] == 0) {
							visited[nx][ny] = total;
							q.push({ nx,ny });
						}
					}
				}

				total++;
				v.push_back(count);
			}
		}
	}

	sort(v.begin(), v.end());

	cout << total - 1 << "\n";
	for (auto ans : v)
		cout << ans << " ";

	return 0;
}

 

 

 

Python)

import sys
from collections import deque

read = sys.stdin.readline
q = deque()

dx = [1,0,-1,0]
dy = [0,1,0,-1]

# 입력받기
m, n, k = map(int, read().rstrip().split())
arr = [ [0] * n for _ in range(m)]
visited = [ [False] * n for _ in range(m)]

# 직사각형 구하기
for _ in range(k):
    y1, x1, y2, x2 = map(int, read().rstrip().split())

    for i in range(x1, x2):
        for j in range(y1, y2):
            arr[i][j] = 1

tot = 0
ans = []

# 영역 구하기
for i in range(m):
    for j in range(n):
        if arr[i][j] == 0 and not visited[i][j]:
            visited[i][j] = True
            q.append((i,j))
            tot += 1
            temp = 0

            while q:
                x, y = q.popleft()
                temp += 1

                for k in range(4):
                    nx = x + dx[k]
                    ny = y + dy[k]

                    if nx < 0 or nx >= m or ny < 0 or ny >= n:
                        continue

                    if arr[nx][ny] == 0 and not visited[nx][ny]:
                        visited[nx][ny] = True
                        q.append((nx,ny))

            ans.append(temp)

ans.sort()

print(tot)
print(' '.join(map(str, ans)))