boj/백준-2583-python

문제

풀이

• m, n, k 그리고 k개의 직사각형의 좌표가 주어질 때, k개의 직사각형 내부를 제외한 나머지 부분이 몇 개의 분리된 영역으로 나누어지는지, 그리고 분리된 각 영역의 넓이가 얼마인지를 구하여 이를 출력하는 프로그램을 작성하라.
  -> DFS로 구현하였다.
  -> 재귀함수를 호출하는데 recursionerror가 나서 이를 피하기 위해 10 * 5로 제귀 깊이를 재설정하였다.
  -> mn 만큼 그래프를 0으로 할당하여 2차원 배열을 만든다.
  -> 사각형 부분을 2차원 배열로 입력 받은 뒤, 2중 반복문으로 그래프에 사각형 영역은 1로 할당한다.
  -> 그래프를 상, 하, 좌, 우를 재귀로 순환하면서 사각형 부분이 아닌 구역을 체크하면서 답을 구하였다.

코드

# https://www.acmicpc.net/problem/2583
# boj, 2583: 영역 구하기, python3
import sys

input = sys.stdin.readline
sys.setrecursionlimit(10**5)  # recursionerror를 피하기 위한 재귀 깊이 변경

m, n, k = map(int, input().split())
coordinate = [list(map(int, input().split())) for _ in range(k)]
graph = [[0] * n for _ in range(m)]
count = 0
result = []

for i in coordinate:
    start_x, start_y, end_x, end_y = i
    for j in range(start_y, end_y):
        for k in range(start_x, end_x):
            graph[j][k] = 1

def dfs(x, y):
    global count
    # 주어진 영역에서만 재귀 함수 호출되도록 조건문 설정
    # if x <= -1 or x >= m or y <= -1 or y >= n:
    if x < 0 or x >= m or y < 0 or y >= n:
        return False

    # 현재 위치 노드가 사각형 영역이면 pass
    if graph[x][y] == 1:
        return False

    # 현재 위치 노드가 사각형 영역이 아닌 구역이면
    graph[x][y] = 1  # 방문했다고 처리
    count += 1
    # 상, 하, 좌, 우 재귀 함수 호출
    dfs(x-1, y)
    dfs(x, y-1)
    dfs(x+1, y)
    dfs(x, y+1)

    return count


for x in range(m):
    for y in range(n):
        cnt = dfs(x, y)
        if cnt:
            result.append(cnt)
            count = 0

print(len(result))
print(*sorted(result))

결과

출처 & 깃허브

boj 2583
github