백준 2583 번. 영역 구하기 (Python / 파이썬)

문제

눈금의 간격이 1인 M×N(M,N≤100)크기의 모눈종이가 있다. 이 모눈종이 위에 눈금에 맞추어 K개의 직사각형을 그릴 때, 이들 K개의 직사각형의 내부를 제외한 나머지 부분이 몇 개의 분리된 영역으로 나누어진다.
예를 들어 M=5, N=7 인 모눈종이 위에 <그림 1>과 같이 직사각형 3개를 그렸다면, 그 나머지 영역은 <그림 2>와 같이 3개의 분리된 영역으로 나누어지게 된다.
<그림 2>와 같이 분리된 세 영역의 넓이는 각각 1, 7, 13이 된다.
M, N과 K 그리고 K개의 직사각형의 좌표가 주어질 때, K개의 직사각형 내부를 제외한 나머지 부분이 몇 개의 분리된 영역으로 나누어지는지, 그리고 분리된 각 영역의 넓이가 얼마인지를 구하여 이를 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 M과 N, 그리고 K가 빈칸을 사이에 두고 차례로 주어진다. M, N, K는 모두 100 이하의 자연수이다. 둘째 줄부터 K개의 줄에는 한 줄에 하나씩 직사각형의 왼쪽 아래 꼭짓점의 x, y좌표값과 오른쪽 위 꼭짓점의 x, y좌표값이 빈칸을 사이에 두고 차례로 주어진다. 모눈종이의 왼쪽 아래 꼭짓점의 좌표는 (0,0)이고, 오른쪽 위 꼭짓점의 좌표는(N,M)이다. 입력되는 K개의 직사각형들이 모눈종이 전체를 채우는 경우는 없다.

출력

첫째 줄에 분리되어 나누어지는 영역의 개수를 출력한다. 둘째 줄에는 각 영역의 넓이를 오름차순으로 정렬하여 빈칸을 사이에 두고 출력한다.

---

문제 풀이

영역 구하기 문제는 직사각형을 그린 후 남은 나머지 영역에 대해

몇 개의 분리된 영역으로 나누어지는지, 그리고 분리된 각 영역의 넓이가 얼마인지를

구하여 출력하는 문제입니다.

 

여기서 주의해야 할 점은 모눈종이의 왼쪽 아래 꼭짓점의 좌표가 (0, 0) 이고

오른쪽 위 꼭짓점의 좌표가 (N, M) 이라는 점입니다.

처음에 이 부분이 약간 헷갈렸었는데

주어진 왼쪽 아래 꼭짓점의 좌표가 (l_x, l_y) 라 하고

오른쪽 위 꼭짓점의 좌표가 (r_x, r_y) 라 할 때,

모눈 종이의 가로를 l_x ~ r_x 까지 칠하고

모눈 종이의 세로를 l_y ~ r_y 까지 칠하면

문제에서 주어진 모눈종이를 위아래로 뒤집은 상태가 되는 것을 알 수 있습니다.

 

위아래로 뒤집힌다 해도 분리된 영역의 개수와 영역의 넓이는 동일합니다. 

따라서 주어진 좌표를 그대로 이용해 2차원 배열의 값을 바꿔주면 됩니다.

2차원 배열의 값을 저는 1로 바꿔주었고, 따라서 분리된 영역은 0인 부분이 됩니다.

 

DFS 알고리즘을 이용하여 분리된 영역의 개수와

각 영역의 넓이를 구해주었습니다.

만약 2차원 배열의 값이 0이라면 그 위치의 상,하,좌,우를 탐색해서

분리된 영역의 개수를 구해주었습니다.

또한 탐색할 때마다 count 변수를 증가시켜 영역의 넓이를 구해주었습니다.

 

분리된 영역을 구할때마다 넓이를 count 한 값을 ans 배열에 삽입해주었고

오름차순으로 정렬해 출력해야 하므로 sort() 함수를 이용했습니다.

 

Python은 재귀한도가 정해져있으므로 

sys.setrecursionlimit() 을 이용해 한도를 늘려주는 것 또한 잊지 말아야 합니다!!!

---

My Code

import sys
sys.setrecursionlimit(1000000)

def dfs(x, y):
    global count  

    if x < 0 or x >= m or y < 0 or y >= n: 
        return False # 범위를 벗어나면 False 반환
    
    if array[x][y] == 0: # 분리된 영역이라면
        count += 1       # 넓이 구하기 위해 count 증가
        array[x][y] = 1  # 방문했다는 의미로 1로 바꿔줌
        # 상, 하, 좌, 우 탐색
        dfs(x - 1, y)    
        dfs(x + 1, y)
        dfs(x, y - 1)
        dfs(x, y + 1)
        return True   # 탐색 완료했다면 True 반환

    return False

m, n, k = map(int,input().split()) # 모눈종이 세로, 가로, 직사각형 개수

array = [[0] * n for _ in range(m)] # 모눈종이
for _ in range(k):
    # 왼쪽 아래 꼭짓점, 오른쪽 위 꼭짓점 좌표
    l_x, l_y, r_x, r_y = map(int,input().split()) 

    for i in range(l_y, r_y):     # 모눈종이의 세로를 y 좌표만큼 
        for j in range(l_x, r_x): # 모눈종이의 가로를 x 좌표만큼
            array[i][j] = 1       # 1로 만들어주기 (직사각형 표시)

result = 0 # 분리된 영역 개수 셀 변수
count = 0  # 각 영역의 넓이를 셀 변수
ans = []   # 넓이를 넣어줄 list
for i in range(m):
    for j in range(n):
        if dfs(i, j):   # 분리된 영역을 구했다면
            result += 1 # 개수 count
            ans.append(count) # 구한 영역의 넓이 삽입
            count = 0         # 영역의 넓이 초기화
ans.sort()  # 각 영역의 넓이 오름차순 정렬

print(result) 
for i in ans:
    print(i, end = ' ')