[파이썬, Python] 백준 2583: 영역 구하기

문제

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

2583번: 영역 구하기

코드

import sys
sys.setrecursionlimit(10**7)

m, n, k = map(int, input().split())
ans = []
paper = [(list(0 for i in range(n))) for i in range(m)]

for _ in range(k):
    x, y, dx, dy = map(int, input().split())
    
    for i in range(x, dx):
        for j in range(y, dy):
            paper[j][i] = 1
            
dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]

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

    return cnt

cnt = 0

for i in range(m):
    for j in range(n):
        if paper[i][j] == 0:
            ans.append(dfs(i, j))
            cnt = 0

print(len(ans))
for i in sorted(ans):
    print(i, end = ' ')

설명

dfs를 통해서 해결했다.
문제의 접근 자체는 굉장히 빠르게 했는데,
x와 y의 범위에 대한 실수가 잦았다.

우선 n, m 만큼의 모눈종이를 0으로 세팅해 준다.
그리고 직사각형의 꼭짓점 좌표를 받아 해당 부분을 1로 처리해 준다.

이후에 dfs를 진행한다.
dfs의 횟수를 체크하기 위해 global을 통해 cnt를 설정해서 카운트해 주었고,
dfs가 종료될 때 cnt값을 리턴하여 정답 리스트에 넣어주었다.

이후 몇 개의 영역으로 나누어지는지를 출력하기 위해 정답 리스트의 개수를 써주었고(dfs의 진행 횟수만큼 영역이 존재)
sorted 된 ans에서 각 영역의 넓이를 출력했다.