BOJ 2583 영역 구하기

https://www.acmicpc.net/problem/2583
시간 1초, 메모리 128MB
input :

• M, N, K(1 <= M, N, K <= 100)
• 왼쪽 아래 꼭짓점의 x, y좌표값과 오른쪽 위 꼭짓점의 x, y좌표값이 빈칸을 사이에 두고 차례로 주어진다.

output :

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

---

문제에서 제일 헷갈렸던 것은, 이 사각형들이 접하는 것을 상하로 뒤집은 다음에 bfs로 탐색을 해가지고 찾으려 했다.
근데 이 y, x / y, x 왼쪽 아래 좌표와, 오른쪽 위의 좌표가 헷갈렸다.

이렇게 y와 x로 입력을 받아서 그 범위안의 그래프 값들을 1로 바꿔주고,
그래프 모든 점을 돌아다니다가 0인 점을 만날 경우 여기에서 그래프 탐색을 하면서 1로 업데이트를 해주자.

import sys
from collections import deque


def bfs(start_x, start_y):
    q = deque([(start_x, start_y)])
    graph[start_x][start_y] += 1

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

    while q:
        x, y = q.popleft()

        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if nx < 0 or nx >= m or ny < 0 or ny >= n:
                continue
            if graph[nx][ny] == 0:
                cnt += 1
                graph[nx][ny] += 1
                q.append((nx, ny))
    return cnt


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

for i in range(k):
    y1, x1, y2, x2 = map(int, sys.stdin.readline().split())

    for x in range(x1, x2):
        for y in range(y1, y2):
            graph[x][y] = 1

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

print(len(ans))
ans.sort()
for item in ans:
    print(item, end=" ")