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

---

1. 코드(DFS)

import sys


def dfs(x, y):
    global width

    if not (0 <= x < m and 0 <= y < n):
        return

    if graph[x][y]:
        graph[x][y] = False
        width += 1
        dfs(x - 1, y)
        dfs(x + 1, y)
        dfs(x, y - 1)
        dfs(x, y + 1)

def convert_pos_left(x, y):
    nx, ny = m - 1, 0  # 시작점: graph[m-1][0]
    nx -= y
    ny += x
    return nx, ny

def convert_pos_right(x, y):
    nx, ny = m - 1, 0
    nx -= y - 1
    ny += x - 1
    return nx, ny


sys.setrecursionlimit(10000)
m, n, k = map(int, sys.stdin.readline().rstrip().split())
graph = [[True] * n for _ in range(m)]
cnt = 0
widths = []

for _ in range(k):
    x1, y1, x2, y2 = map(int, sys.stdin.readline().rstrip().split())
    left_r, left_c = convert_pos_left(x1, y1)
    right_r, right_c = convert_pos_right(x2, y2)

    for i in range(right_r, left_r + 1):
        for j in range(left_c, right_c + 1):
            graph[i][j] = False  # 직사각형 색칠

for i in range(m):
    for j in range(n):
        if graph[i][j]:
            width = 0
            cnt += 1
            dfs(i, j)
            widths.append(width)
            width = 0

print(cnt)
for w in sorted(widths):
    print(w, end=' ')

2. 코드(BFS)

import sys
from collections import deque


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

    return width


def convert_pos_left(x, y):
    nx, ny = m - 1, 0  # 시작점: graph[m-1][0]
    nx -= y
    ny += x
    return nx, ny

def convert_pos_right(x, y):
    nx, ny = m - 1, 0
    nx -= y - 1
    ny += x - 1
    return nx, ny


sys.setrecursionlimit(10000)
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

m, n, k = map(int, sys.stdin.readline().rstrip().split())
graph = [[True] * n for _ in range(m)]
cnt = 0
widths = []

for _ in range(k):
    x1, y1, x2, y2 = map(int, sys.stdin.readline().rstrip().split())
    left_r, left_c = convert_pos_left(x1, y1)
    right_r, right_c = convert_pos_right(x2, y2)

    for i in range(right_r, left_r + 1):
        for j in range(left_c, right_c + 1):
            graph[i][j] = False  # 직사각형 색칠

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

print(cnt)
for w in sorted(widths):
    print(w, end=' ')

3. 후기

2차원 좌표평면을 파이썬에서 사용하는 2차원 배열으로 변환시키는 부분이 어려웠다.
하나의 공식으로는 2차원 배열 속 좌표로 변환할 수 없다는 걸 깨닫고 함수를 따로따로 만들었다.

convert_pos_left: 왼쪽 하단 좌표를 변환하는 함수
convert_pos_right: 오른쪽 상단 좌표를 변환하는 함수