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

백준 - 2583 영역 구하기

풀이

1. m * n 크기의 행렬을 만들고 1로 채움 (1: 셀 수 있는 영역)

2. 입력받는 좌표 정보를 y1, x1, y2, x2로 저장 -> 사각형의 좌표가 됨
   -> 사각형을 0으로 채움 (0: 셀 수 없는 영역)

3. 완성된 그래프를 bfs 탐색하면서 연결 성분의 개수를 구해줌

코드

from sys import stdin
from collections import deque

m, n, k = map(int, stdin.readline().split())
graph = [[1 for i in range(n)] for i in range(m)]

for i in range(k):
    y1, x1, y2, x2 = map(int, stdin.readline().split())
    for i in range(x1, x2):
        for j in range(y1, y2):
            graph[i][j] = 0

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

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

answer = []
for x in range(m):
    for y in range(n):
        if graph[x][y]:
            answer.append(bfs(x, y))

print(len(answer))
for i in sorted(answer):
    print(i, end=' ')