백준 2583번 : 영역 구하기 in Python

2583번: 영역 구하기

 

www.acmicpc.net

이 문제는 M*N 크기의 모눈종이가 있고 여기에 K개의 직사각형을 그릴 때 K개의 직사각형의 내부를 제외한 나머지 부분이 여러 개의 영역으로 나누어지는데, 이때 영역의 개수와 각 영역의 넓이를 구하는 문제이다.

이를 해결하기 위해서는 우선 모눈종이의 각 칸이 하나의 entry에 대응하는 M*N 행렬 paper를 만들고, 직사각형의 내부의 칸에 대응하는 entry의 값을 1로, 나머지 entry는 0으로 한다. 이때 문제에서 나오는 input은 직사각형의 왼쪽 아래의 좌표와 오른쪽 위 좌표가 주어지는데, 실제로 paper의 각 entry는 하나의 칸에 대응하고, entry의 행과 열은 각각 모눈종이 내 해당 칸의 왼쪽 아래 점의 y좌표, x좌표와 같다. 따라서 직사각형에 대응하는 칸들을 찾을 때 왼쪽 아래 점이 (x1, y1), 오른쪽 위 점이 (x2, y2)로 주어질 때 paper 내 entry 중 [x1, x2-1]*[y1, y2-1]에 해당하는 entry를 1로 바꿔준다.

그 다음 영역의 개수와 각 영역의 넓이를 구하기 위해 그래프 탐색을 이용해야 한다. 즉, paper 내 모든 entry에 대해 방문하지 않은 영역이 있을 경우 그 entry에 대응하는 칸과 연결된 모든 영역 내 칸들을 방문하면서 영역의 칸의 개수, 즉 영역의 넓이를 구한다. 그리고 해당 영역을 이미 방문했다는 표시를 남겨둬 후에 영역 내 다른 entry를 방문했을 때 해당 영역을 다시 탐색하는 일이 없도록 한다.

이를 코드로 구현하면 다음과 같다.

import sys
sys.setrecursionlimit(10**5)
M, N, K = map(int, input().split())
# 모눈종이를 나타내는 행렬
paper = [[0]*N 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):
            paper[i][j] = 1
# 방문하지 않은 영역의 넓이를 구하기 위해 DFS를 구현한 함수  
def DFS(x, y):
    global M, N
    # 해당 칸을 이미 방문했거나 직사각형 내부의 칸인 경우 0을 반환한다.
    if visited[y][x] or paper[y][x] == 1: return 0
    visited[y][x] = True
    # 영역의 넓이를 나타내는 변수
    res = 1
    dx = [1, -1, 0, 0]
    dy = [0, 0, 1, -1]
    for i in range(4):
        next_x = x + dx[i]
        next_y = y + dy[i]
        if 0<=next_x<N and 0<=next_y<M and paper[next_y][next_x] == 0:
            res += DFS(next_x, next_y)
    return res
# 영역의 개수
cnt = 0
# 각 영역의 넓이를 저장하는 배열
area = []
visited = [[False]*N for _ in range(M)]
for i in range(M):
    for j in range(N):
        if paper[i][j] == 0 and not visited[i][j]:
            cnt += 1
            area.append(DFS(j, i))
area.sort()
print(cnt)
print(" ".join(map(str, area)))