[Python] 백준 2583번: 영역 구하기

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

2583번: 영역 구하기

 

 

---

문제 설명

M X N 크기의 모눈종이가 있다. (M, N <= 100)

모눈종이 위에 K개의 직사각형을 그리면, 직사각형 내부를 제외한 나머지 부분들이 몇 개의 분리된 영역으로 나누어진다.

 

 

왼쪽 그림을 보면,

1번, 2번, 3번이 색칠되지 않은 분리된 영역이다.

분리된 세 영역의 크기는 1, 7, 13인데

M, N, K 그리고 좌표값들이 주어질 때, 색칠되지 않은 부분이 몇개의 분리된 영역으로 나누어지는지, 그리고 각 분리된 영역의 넓이를 크기 순(오름차순)으로 나열하여 출력하면 된다. 

 

 

 

---

풀이 방법

board 를 변수명으로 갖는 2차원 배열을 정의하려고 한다.

처음에는 element(=요소)들이 모두 False 값을 가지고 있다.

직사각형 내부에 해당하는 값들만 True로 바꿔준다.

 

좌표의 맨 위, 맨 왼쪽을 (0, 0)으로 생각하는 것이 편하기 때문에

처음의 모눈종이를 상하 반전시켰다. (분리된 영역의 넓이를 구하는 것이기 때문에, 단순 회전은 값에 영향을 주지 않는다.)

 

 

이 다음부터는, 반복문으로 구현한 dfs함수를 이용해서 각 영역의 넓이값을 구해주면 된다.

 

stack에 포함시킬 때, 방문한 포인트를 True값으로 변환해주면 된다.

가령, stack에서 좌표값을 pop() 하고 나서, 바로 방문 포인트를 True값으로 변환하는 실수를 범할 수도 있는데

이렇게 할 경우, 넓이값이 더 크게 나올 수도 있다. (왜인지는 직접해보면 안다)

 

 

 

---

Code

# import sys
# input = sys.stdin.readline
 
def dfs(x, y):
    stack = [(x, y)]
    board[x][y] = True
    num = 1
 
    while stack:
        x, y = stack.pop()
        for dx, dy in zip(dxs, dys):
            nx, ny = x+dx, y+dy
            if nx<0 or nx>=n or ny<0 or ny>=m: continue
            if not board[nx][ny]:
                stack.append((nx, ny))
                board[nx][ny] = True
                num += 1
    ## 마지막에 영역의 크기를 리스트에 저장한다.
    empty_list.append(num)
 
 
if __name__ == '__main__':
    n, m, k = map(int, input().split())
    board = [[False] * m for _ in range(n)]
 
    ## 직사각형이 존재하는 영역은 True로 변환
    for _ in range(k):
        y1, x1, y2, x2 = map(int, input().split())
        for i in range(x1, x2):
            for j in range(y1, y2):
                board[i][j] = True
    ## 동 남 서 북
    dxs = (0, 1, 0, -1)
    dys = (1, 0, -1, 0)
 
    empty_list = []
    for i in range(n):
        for j in range(m):
            if not board[i][j]: # False 라면
                dfs(i, j)       # 영역의 크기를 empty_list에 추가시키는 함수
 
    print(len(empty_list))
    print(' '.join(map(str, sorted(empty_list))))