백준 2583번 파이썬

문제 링크

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

2583번: 영역 구하기

 

시간 제한 / 메모리 제한

1 초

128 MB

 

문제

눈금의 간격이 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개의 직사각형들이 모눈종이 전체를 채우는 경우는 없다.

출력

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

예제 입력

5 7 3
0 2 4 4
1 1 2 5
4 0 6 2

예제 출력

3
1 7 13

 

문제 풀이를 위해 생각한 것

1. 우선 모눈종이 위에 직사각형을 표시한다.
2. 모눈종이 각 원소를 확인하며, 직사각형이 표시되지 않은 영역을 찾아 DFS 혹은 BFS를 수행한다.
3. DFS 수행 횟수는 분리된 영역의 수이고, 각 DFS의 리턴 값은 영역의 크기이다.
4. 문제에서 제시하는 y좌표는 좌하단에서부터 0이라는 것에 주의해야 한다.

 

사용한 자료구조 / 알고리즘

2차원 배열 / DFS(재귀)

 

풀이 코드

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)

n, m, k = map(int, input().split())
board = [[1 for _ in range(m)] for _ in range(n)]
visited = [[False for _ in range(m)] for _ in range(n)]

# n = y = 세로축, m = x = 가로축
# 문제에서 주어지는 y좌표는 왼쪽 하단부터 0
for _ in range(k):
    lx, ly, rx, ry = map(int, input().split())
    for i in range(n-ry, n-ly): # 오른쪽 상단 꼭짓점 index부터, 왼쪽 하단 꼭짓점 - 1 index까지
        for j in range(lx, rx): # 왼쪽 하단 꼭짓점 index부터, 오른쪽 상단 꼭짓점 - 1 index까지
            board[i][j] = 0  # 직사각형을 0으로 표시

dy = (1, -1, 0, 0)
dx = (0, 0, 1, -1)
cnt = 0
cntList = []

def dfs(y, x):
    visited[y][x] = True
    _cnt = 1

    for i in range(4):
        ny = y + dy[i]
        nx = x + dx[i]
        if 0 <= ny < n and 0 <= nx < m and board[ny][nx] == 1 and not visited[ny][nx]:
            _cnt += dfs(ny, nx)

    return _cnt

for i in range(n):
    for j in range(m):
        if board[i][j] == 1 and not visited[i][j]:
            cnt += 1
            cntList.append(dfs(i, j))

cntList.sort()
print(cnt)
for c in cntList:
    print(c, end=' ')

 

시간 복잡도 분석

O(N^2).

N, M, K <= 100이고, N*M 좌표를 모두 탐색해야 하기 때문에, 시간 복잡도는 O(N^2)이다.

 

문제에서 중요한 부분

보통 편의를 위해 세로축을 x, 가로축을 y로 설정하고, 세로축의 index가 좌상단부터 0인 일반적인 2차원 배열 탐색 문제와 달리, 본 문제에서는 수학에서와 같이 y좌표가 좌하단부터 0으로 제공되었다.

 

따라서 입력을 받을 때와 직사각형을 표시할 때 모두 이를 고려해야 했으며, 2차원 배열의 원소에 접근할 때도 혼선이 생기지 않도록 [x][y]가 아닌 [y][x]로 접근했다.