[Python] 영역 구하기 - 백준 (DFS)

해당 글은 백준 2583번 문제 '영역 구하기'를 다룬다.

문제

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

2583번: 영역 구하기

 

설명

해당 문제는 모눈종이가 없는 모든 행, 열을 DFS로 탐색해서 영역이 몇 개인지, 넓이는 얼마인지 출력하는 문제이다.

발생한 영역마다 넓이를 저장하는 result 변수에서 길이가 총 영역의 갯수이고, 넓이를 오름차순으로 출력해야하므로 정렬을 한 후에 순서대로 출력해줘야한다.

그리고 DFS로 풀었을 때, 런타임 에러가 발생하므로 재귀한계를 10000으로 설정해야한다.

 

코드

import sys
sys.setrecursionlimit(10000)

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

for i in range(k):
    y1, x1, y2, x2 = map(int, input().split())
    for x in range(x1, x2):
        for y in range(y1, y2):
            graph[x][y] = -1

dx = [-1, 1, 0, 0]
dy = [0, 0, 1, -1]
def dfs(x, y, cnt):
    graph[x][y] = cnt
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if nx >= 0 and nx < m and ny >= 0 and ny < n and graph[nx][ny] == 0:
            cnt += 1
            cnt = dfs(nx, ny, cnt)
    return cnt

result = []

for i in range(m):
    for j in range(n):
        if graph[i][j] == 0:
            result.append(dfs(i, j, 1))

result.sort()
print(len(result))
for i in result:
    print(i, end=' ')