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

문제

모눈종이 위에 k개의 직사각형을 그릴 때, 직사각형이 그려지지 않은 부분이 몇 개의 분리된 영역으로 나누어진다.

예를 들어 m = 5, n = 7 인 모눈종이 위에 3개의 직사각형을 그렸을 때, 다음과 같이 3개의 영역으로 나누어질 수 있다.
각각의 넓이는 1, 7, 13이다.
이와 같이 직사각형에 포함되지 않는 분리된 영역의 각 크기를 오름차순으로 출력하는 문제이다.

풀이

• 먼저 주어진 직사각형을 모눈종이 영역에 표시한다.
  • 이때 본 문제에서는 상하좌우 방향을 유의해야 한다.
  • 여기서는 직사각형이 차지하는 공간이 중요한 부분임으로 
    임의로 row를 m, col를 n으로 보고,
    왼쪽 아래 꼭짓점의 x1, y1좌표값과 오른쪽 위 꼭짓점의 x2, y2좌표값을 왼쪽 위, 오른쪽 아래로 가정하였다.
    (편의상 상하반전한 상태로 가정함)
• 모눈종이를 순회하면서 직사각형에 포함되지 않는 영역의 크기를 dfs를 통해 구한다. (bfs도 가능)
• 별도 리스트에 담아 개수와 영역의 크기를 정렬하고 출력한다.

알고리즘

1. 영역의 크기를 구하기 위한 DFS를 정의한다.
   • 스택에 시작점을 담는다.
   • 시작점을 카운트(cnt)하고, 1로 값을 입력하여 방문을 체크한다.
   • 스택에서 좌표를 꺼내면서 상하좌우를 탐색한다.
   • 이때 모눈종이 바깥과 직사각형 혹은 방문한 영역을 제외하고 탐색한다.
   • 이동 가능한 위치라면 스택에 담으며 방문을 체크(1)하고, 영역 크기(cnt)를 더해준다.
   • 스택에 더 이상 남은 좌표가 없다면 영역 크기를 return 한다.
2. 모눈종이 영역을 0으로 초기화한다.
3. 주어진 직사각형 좌표를 통해 직사각형을 표시한다.
   • for문을 돌면서 1을 입력한다.
4. (0,0)부터 (m, n)까지 순회하면서 비어있는 곳이라면 앞서 정의한 DFS를 통해 비어있는 영역의 크기를 구한다.
5. 구한 값을 areas 리스트에 담는다.
6. 영역의 개수를 출력한다.
7. sort를 통해 오름차순으로 정렬한 영역의 크기들을 출력한다.

Python 코드

import sys
input = sys.stdin.readline

# 모눈종이 안의 범위인지 체크
def in_range(x,y):
    return 0<=x<m and 0<=y<n

# dfs 를 사용해 영역의 크기를 세준다.
def dfs(i, j):
    stack = [(i, j)]
    dx, dy = (0, 0, 1, -1), (1, -1, 0, 0)
    cnt = 1
    arr[i][j] = 1
    while stack:
        x, y = stack.pop()
        for d in range(4):
            nx, ny = x + dx[d], y + dy[d]
            if not in_range(nx,ny): # 모눈종이 바깥 제외
                continue
            if arr[nx][ny]: # 직사각형 및 방문 영역 제외
                continue
            cnt += 1
            stack.append((nx, ny))
            arr[nx][ny] = 1
    return cnt


m, n, k = map(int, input().split())
# 빈공간이면 0 직사각형이 있으면 1
arr = [[0] * n for _ in range(m)]
# 직사각형에 해당하는 범위 색칠
for _ in range(k):
    y1, x1, y2, x2 = map(int, input().split())
    for i in range(x1, x2):
        for j in range(y1, y2):
            arr[i][j] = 1

# dfs를 통해 분리된 영역 넓이 구하기
areas = []
for i in range(m):
    for j in range(n):
        if not arr[i][j]:
            areas.append(dfs(i, j))

print(len(areas)) # 영역 개수
areas.sort() # 오름차순 정렬
print(*areas) # 영역 크기

 

문제출처

2583번: 영역 구하기