[python] 백준 2583 영역 구하기

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

2583번: 영역 구하기

 

문제 해결

• 사각형으로 영역을 막아놓고 나머지 빈 구역의 개수를 구하고 각 영역의 크기를 구하면 되는 문제
• bfs를 이용해 영역을 메우면서 쉽게 풀 수 있다.

 

CODE

from collections import deque

def bfs(x,y):
    global visited
    que = deque()
    que.append((x,y))
    visited[y][x] = 1
    cnt = 1
    dxs = [-1, 1, 0, 0]
    dys = [0, 0, -1, 1]
    while que:
        now_x, now_y = que.popleft()
        for dx, dy in zip(dxs, dys):
            new_x = now_x + dx
            new_y = now_y + dy
            if 0<=new_x<n and 0<=new_y<m and visited[new_y][new_x] ==0:
                visited[new_y][new_x] = 1
                cnt += 1
                que.append((new_x,new_y))
    return cnt
if __name__=='__main__':
    m, n ,k = map(int, input().split()) # y ,x 사각형 개수
    visited = [[0]*n for _ in range(m)]
    ans = 0
    result = []
    for _ in range(k):
        min_x,min_y,max_x,max_y = map(int, input().split())
        for i in range(min_x,max_x):
            for j in range(min_y,max_y):
                visited[j][i] = 1
    for i in range(n):
        for j in range(m):
            if visited[j][i] ==0:
                a = bfs(i,j)
                result.append(a)
                ans += 1
    result.sort()
    print(ans)
    print(*result)