[알고리즘] 백준 2583 - 영역구하기

문제

영역 구하기

 

접근

1. 왼쪽 하단 좌표 ~ 오른쪽 상단 좌표가 각 주워지면 이를 통해서 직사각형의 넓이를 구해야한다

2. 2차원 배열을 두고 0으로 초기화를 한 상태에서 넓이 사이에 해당함을 이중 for문으로 찾아서 1을 넣어준다

3. dfs문으로 통해 나머지 부분의 총 개수를 dfs == True인 경우마다 올리면서, dfs가 돌아갈때마다 각 영역의 넓이를 구해준다

4. 구한 넓이들을 배열에 넣고 정렬을 하여 출력하면 된다

 

풀이

import sys
sys.setrecursionlimit(10**9)

# 세로가 m
m, n, k = map(int, input().split())

board = [[0]*(n+1) for _ in range(m+1)]

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

num = 0
count = []


def dfs(x, y):
    global num
    if 0 <= x < m and 0 <= y < n and board[x][y] == 0:
        board[x][y] = 1
        num += 1
        dfs(x-1, y)
        dfs(x+1, y)
        dfs(x, y-1)
        dfs(x, y+1)
        return True
    return False


res = 0
for i in range(m):
    for j in range(n):
        if dfs(i, j) == True:
            res += 1
            count.append(num)
            num = 0

count.sort()

print(res)
for i in count:
    print(i, end=' ')