백준 2583 영역 구하기

과정

• 2차원 배열에서 K개의 직사각형 영역을 visited 처리하기
• bfs로 영역의 개수와 각 영역의 너비 구하기

import sys
from collections import deque

input = sys.stdin.readline
M, N, K = map(int, input().split())
map_lst = [[False] * N for _ in range(M)]

for _ in range(K):
    lx, ly, rx, ry = map(int, input().split())
    for i in range(lx, rx):
        for j in range(ly, ry):
            map_lst[j][i] = True

# 상 우 하 좌
dx = [0, 1, 0, -1]
dy = [1, 0, -1, 0]

def bfs(x, y):
    cnt = 1
    queue = deque([[x, y]])
    map_lst[y][x] = True
    while queue:
        a = queue.pop()
        x = a[0]
        y = a[1]
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0<=nx<N and 0<=ny<M and not map_lst[ny][nx]:
                map_lst[ny][nx] =True
                cnt += 1
                queue.append([nx, ny])
    return cnt
ans_lst = []
ans = 0
for i in range(N):
    for j in range(M):
        if not map_lst[j][i]:
            ans_lst.append(bfs(i, j))
            ans += 1
            
ans_lst.sort()
print(ans)
print(*ans_lst)