백준 2583번 : 영역 구하기(python)

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

2583번: 영역 구하기

 

m,n,k = map(int,input().split())
data = [[0]*n for _ in range(m)]
dx = [-1,1,0,0]
dy = [0,0,-1,1]

for _ in range(k):
    a1,a2,b1,b2 = map(int,input().split())

    for j in range(a1,b1):
        for k in range(a2,b2):
            data[k][j] = 1

def dfs(x,y):
    count = 1
    q = [(x,y)]
    data[x][y] = 1
    while q:
        x,y = q.pop()
        for i in range(4):
            nx,ny = x+dx[i],y+dy[i]
            if 0<=nx<m and 0<=ny<n and data[nx][ny]==0:
                data[nx][ny] = 1
                q.append((nx,ny))
                count += 1
    return count

result = 0
number = []
for i in range(m):
    for j in range(n):
        if data[i][j] == 0:
            result += 1
            c = dfs(i,j)
            number.append(c)

print(result)
number.sort()
print(*number)