[파이썬] 백준 알고리즘 No.2583 영역 구하기

나의 코드

import sys
from collections import deque
input = sys.stdin.readline
n, m, k = map(int, input().split())

maps = [[False] * m for _ in range(n)]
visited = [[0] * m for _ in range(n)]
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]
count = 1

for _ in range(k):
    x1, y1, x2, y2 = map(int, input().split())
    a1, b1, a2, b2 = (n - y1), x1, (n - y2), x2

    for i in range(min(a1, a2), max(a1, a2)):
        for j in range(min(b1, b2), max(b1, b2)):
            maps[i][j] = True


def bfs(a, b):
    global count
    queue = deque()
    queue.append((a, b))
    visited[a][b] = count

    while queue:
        x, y = queue.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < n and 0 <= ny < m and not maps[nx][ny]:
                if visited[nx][ny] == 0:
                    visited[nx][ny] = count
                    queue.append((nx, ny))


for i in range(n):
    for j in range(m):
        if visited[i][j] == 0 and not maps[i][j]:
            bfs(i, j)
            count += 1

result = []
for i in range(1, count):
    tmp = 0
    for visit in visited:
        tmp += visit.count(i)
    result.append(tmp)

print(count - 1)
print(*sorted(result))

 

풀이 방법

우리가 사용하는 2차원 배열과, 주어진 직사각형의 (x1, y1) 좌표 (x2, y2)좌표의 좌표계 관점이 다르다.

따라서 a1, b1, a2, b2 = n - y1, x1, n - y2, x2 로 변환하여야 한다.

변환된 좌표계에 bfs를 통해 구역을 분리해준 뒤, 구역 번호에 맞게 숫자를 카운트하여 값을 내주면 되는 간단한 문제