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

링크

백준 2583 영역구하기

이제 정말 이런류의 dfs 문제는 고민안하고 풀수있다! (물론 아직 더 심한 문제를 못만나서 이러는게 맞다.)
주어지는 좌표가 상하로 반전돼서 주어지는데 사실 그대로 입력받아서 사용해도 상관없다. 모양이 중요하기 때문이다.
해당문제에서 처음으로 recursionError를 만났는데 최대 재귀 깊이를 조절해주니 해결됐다.

정답 코드

import sys
sys.setrecursionlimit(100000) #없으면 recursion error 발생

def dfs(r, c):
    global cnt
    visit[r][c] = 1
    for i in range(4):
        nr = r + dr[i]
        nc = c + dc[i]
        if 0 <= nr < M and 0 <= nc < N and visit[nr][nc] == 0:
            cnt += 1
            dfs(nr, nc)

M ,N, K = map(int, input().split())

visit = [[0] * N for _ in range(M)]

for _ in range(K):
    sc, sr, ec, er = map(int, input().split()) #굳이 뒤집지 않음 상하 반전이지만 어차피 모양은 똑같을테니까
    for i in range(sr, er):
        for j in range(sc, ec):
            visit[i][j] = 1

#12시부터 시계방향
dr = [-1, 0, 1, 0]
dc = [0, 1, 0, -1]
cnt = 1 #넓이
area = 0 #영역의 갯수
ans = []

for i in range(M):
    for j in range(N):
        if visit[i][j] == 0:
            area += 1
            dfs(i, j)
            ans.append(cnt)
            cnt = 1 #넓이 초기화

ans.sort()
print(area)
print(' '.join(map(str, ans)))

알게된 것👨‍💻

• sys.setrecursionlimit() 을 사용하면 최대 재귀 깊이를 늘릴 수 있다.