BOJ 2583번 : 영역 구하기 (Python/Silver 1)

2583번: 영역 구하기

---

설명

M×N 모눈종이에서 K개의 직사각형이 있고, 그 직사각형 부분을 제외한 나머지 영역의 개수와 넓이를 구하면 된다.

 

풀이

✓ 그래프 탐색 - DFS로 풀이

 

Solution

#18:35 - 19:17 -> 풀이봄 19:57 제출

import sys
input = sys.stdin.readline

sys.setrecursionlimit(10**9) #->런타임 에러 방지/재귀 깊이 변경

M, N, K = map(int, input().split())
graph = [[0]*N for _ in range(M)] #모눈종이

for _ in range(K):
    x1, y1, x2, y2 = map(int, input().split()) #입력 받기
    for i in range(y1, y2):
        for j in range(x1, x2):
            graph[i][j] = 1 # 사각형인 부분만 방문 처리
#상하좌우
dx = [-1, 1, 0, 0]
dy = [0, 0, 1, -1]
#d = [(1, 0), (0, -1), (-1, 0), (0, 1)]

def DFS(x, y, cnt):
    graph[y][x] = 1 #사각형이 아닌 부분 방문 처리
    
    #주변 탐색(같은 영역인지 탐색)
    #for dy, dx in d:
    #    ny, nx = y + dy, x + dx
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]

        if -1 < nx < N and -1 < ny < M and graph[ny][nx] == 0: #사각형이 아닌 곳
                cnt = DFS(nx, ny, cnt+1)
    return cnt

res = []
for i in range(M):
    for j in range(N):
        if graph[i][j] == 0: #사각형이 아닌 곳만 탐색
            res.append(DFS(j, i, 1)) #분리된 영역이 하나라도 있으면 탐색을 하기 때문에 카운트 1
print(len(res))
print(*sorted(res)) #asterisk(*) - unpack