문제

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

나의 코드 (답안 참조)

"""
1. 아이디어
문제에 명시된 좌표가 프로그래밍에서 쓰는 좌표랑 좀 달라서 신경 써줘야 하고
영역 구하는 부분은 bfs를 탐색하면서 개수를 세주고 빈 리스트에 집어넣고 마지막에
출력하면 된다.

2. 시간복잡도
초반부에 나오는 3중 for문 때문에 O(N^3)인것 같긴 한데 n, m, k가 전부 100이하의
자연수 이기 때문에 3중 for문이여도 상관없는거 같다.
"""

from collections import deque
from sys import stdin
input = stdin.readline

n, m, k = map(int, input().split())
paper = [ [0] * m for _ in range(n) ]
answer = []

for _ in range(k):
    x1, y1, x2, y2 = map(int, input().split())
	
    """ 문제에서 일반적인 좌표와 다르게 설정했으므로 다음 반복문을 통해 뒤집어 준다.
    (이해하기 힘듦 - 직접 수식계산하면 나옴) """
    for i in range(n-y2, n-y1):
        for j in range(x1, x2):
            paper[i][j] = 1 # 직사각형을 색칠해줌.

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

def bfs(x, y):
    paper[x][y] = 2
    cnt = 1
    q = deque([(x, y)])

    while q:
        px, py = q.popleft()

        for k in range(4):
            mx = px + dx[k]
            my = py + dy[k]

            if 0 <= mx < n and 0 <= my < m:
                if paper[mx][my] == 0:
                    paper[mx][my] = 2 # 따로 visited 배열을 안쓰고 2를 대입해서 방문여부를 체크한다.
                    cnt += 1
                    q.append((mx, my))

    answer.append(cnt)

for i in range(n):
    for j in range(m):
        if paper[i][j] == 0:
            bfs(i, j)

print(len(answer))
print(*sorted(answer))

    

느낀점

문제에 적힌 좌표가 일반적으로 프로그래밍에서 작성하는 좌표랑 달라서 헷갈린 문제이다. bfs 자체는 그냥 쉬운문제이다.