문제: 2583 영역 구하기

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

Solution

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

m, n, k = map(int, input().split())

graph = [[0] * n for _ in range(m)]

for _ in range(k):
    x1, y1, x2, y2 = list(map(int, input().split()))
    for i in range(y1, y2):
        for j in range(x1, x2):
            graph[i][j] = 1

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

def bfs(x, y):
    queue = deque()
    queue.append((x, y))
    graph[x][y] = 1
    cnt = 1

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


result = []
for i in range(m):
    for j in range(n):
        if graph[i][j] == 0:
            result.append(bfs(i, j))

result.sort()
print(len(result))
for i in result:
    print(i, end= ' ')

배운점

풀이는
1. 배열안에 m * n 크기의 2차원 배열을 만들고 [0]으로 초기화.
2. 모눈종이 안의 직사각형영역에 1을 채운다.
3. (0, 0) 부터 bfs를 돌며 0인 분리된 부분의 크기를 구해 빈 배열에 넣는다.
4. 정렬후 크기를 출력

이 문제는 기존에 풀었던 n x m방식에서 반대인 m x n방식 인 점과 (0, 0)의 위치가 왼쪽 상단이 아닌 왼쪽 하단이었다는게 문제를 처음 봤을 때 당황했던 점이다.
하지만 간단하게 생각해 보면 어떤게 행 이고 어떤게 열 인지만 파악하면 기존에 풀었던 방식과 다를게 없는 문제였다.
문제에 쫌 더 익숙 해 질 필요가 있을것 같다.