백준 2583 - 영역 구하기 Python

import sys
sys.setrecursionlimit(50000)
M, N, K = map(int,input().split())
arr = [[0] * (N+1) for _ in range(M+1)]
dx, dy = [1,-1,0,0],[0,0,1,-1]

def dfs(arr,i,j):
    cnt = 1
    for k in range(4):
        i_ = i + dx[k]
        j_ = j + dy[k]
        if 0<=i_<M and 0<=j_<N:
            if arr[i_][j_] == 0:
                arr[i_][j_] = -1
                cnt += dfs(arr,i_,j_)
    return cnt

for k in range(K):
    uX_, uY, tX, tY = map(int,input().split())
    while uY < tY:
        uX = uX_
        while uX  < tX:
            arr[M-1-uY][uX] = 1
            uX += 1
        uY += 1

square = 0
answer = []
for i in range(M):
    for j in range(N):
        if arr[i][j] == 0:
            arr[i][j] = -1
            answer.append(dfs(arr,i,j))
            square += 1
        
print(square)
answer.sort()
for i in range(len(answer)):
    print(answer[i], end = ' ')

이 문제에서 좌표는 왼쪽 위가 기준이 아니라 왼쪽 아래에서 0,0으로 시작합니다.

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

왼쪽은 문제에서 좌표, 오른쪽은 배열을 기준으로 인덱스입니다.

k 반복문에서

첫 번째 입력 0,2,4,4를 기준으로 확인해보면

uX는 0, tX는 4 uY는 2, tY는 4가 됩니다.

처음 반복에서 M-1-uY = 5-1-2 = 2가 돼서 arr[2][0]부터 arr[2][3]까지 1이 됩니다.

그다음으로 uY를 증가시켜서 M-1-uY = 5-1-3=1이 돼서 arr[1][0]부터 arr[1][3]까지 1로 됩니다.

 

1,1,2,5로 다시 확인해보겠습니다.

uX는 1, tX는 2 uY는 1 tY는 5입니다.

M-1-uY = 5-1-1 = 3이므로 arr[3][1]이 1로 됩니다.

uX에서 1을 더하면 tX를 넘어가므로 X축을 채우는 반복문은 한 번만 돌아갑니다.

그다음 반복문은 M-1-uY = 5-1-2=2로 arr[2][1]이 1로 되고 이렇게 uY가 4까지 올라가면 arr[0][1]이 1로 올라갑니다.

 

직사각형 영역을 채우는게 어렵지 나머지는 어렵지 않습니다!

1로 마킹하지 않은 부분만 dfs로 확인하면 됩니다.