[Python] 백준 2583번 영역 구하기

문제

2583번: 영역 구하기

입력

• 첫째 줄에 M과 N, 그리고 K가 빈칸을 사이에 두고 차례로 주어진다. M, N, K는 모두 100 이하의 자연수이다. 둘째 줄부터 K개의 줄에는 한 줄에 하나씩 직사각형의 왼쪽 아래 꼭짓점의 x, y좌표값과 오른쪽 위 꼭짓점의 x, y좌표값이 빈칸을 사이에 두고 차례로 주어진다. 모눈종이의 왼쪽 아래 꼭짓점의 좌표는 (0,0)이고, 오른쪽 위 꼭짓점의 좌표는(N,M)이다. 입력되는 K개의 직사각형들이 모눈종이 전체를 채우는 경우는 없다.

출력

• 첫째 줄에 분리되어 나누어지는 영역의 개수를 출력한다. 둘째 줄에는 각 영역의 넓이를 오름차순으로 정렬하여 빈칸을 사이에 두고 출력한다.

입력 예제

5 7 3
0 2 4 4
1 1 2 5
4 0 6 2

출력 예제

3
1 7 13

문제 풀이

• 그래프에서 정사각형이 있는 칸을 1로 만든 후 0으로 되어있는 빈칸만 탐색
• 정사각형의 넓이만 구하면 되므로 배열을 따로 조작할 필요 없이 그냥 입력 받아서 탐색하면 된다.
• 그래프의 값이 0일 때 너비우선 탐색을 진행하고, 탐색을 진행할 때마다 새로운 칸을 탐색하게 된다면 영역이 한 칸 늘어난 것이므로 영역개수를 하나씩 늘린다.
• 마지막으로 모든 영역의 개수를 저장할 리스트를 만들어 저장한 후 탐색을 종료한다.
• 모든 탐색을 마친 후 탐색이 진행된 횟수가 영억의 개수이므로 출력한 후, 저장되어있는 각 영역의 개수들을 오름차순으로 출력한다.

코드

from collections import deque
dy = [-1,1,0,0]
dx = [0,0,-1,1]
m,n,k = map(int,input().split())
graph = [[0] * n for _ in range(m)]
for _ in range(k):
    x1, y1, x2, y2 = map(int,input().split())
    for i in range(y1, y2):
        for j in range(x1, x2):
            graph[i][j] = 1

result = []
def bfs(y,x):
    queue = deque()
    queue.append((y,x))
    graph[y][x] = 1
    cnt = 1
    while queue:
        y,x = queue.popleft()
        for i in range(4):
            ny = y + dy[i]
            nx = x + dx[i]
            if 0 <= ny < m and 0 <= nx < n and graph[ny][nx] == 0:
                graph[ny][nx] = 1
                cnt += 1
                queue.append((ny,nx))

    result.append(cnt)

cnt = 0
for i in range(m):
    for j in range(n):
        if graph[i][j] == 0:
            bfs(i,j)
            cnt += 1

print(cnt)
result.sort()
print(*result)