[백준_2583] 영역 구하기 python

dfs 문제를 풀때마다 느끼는거지만,

파이썬의 최대 리커전가능 횟수 디폴트값이 1000인건,

너무 야박한 것 같다.

 

꼭지점 좌표로 입력 받을 때,

역으로 이를 생각해야 하기에 조금 불편하겠다 싶었는데,

곰곰히 생각해보니 점대칭으로 그냥 받아도 아무차이없을 것 같아,

그대로 해봤더니 성공했다.

 

# n, m, k 입력
n, m, k = map(int, input().split())

# grid
grid = [
    [0] * m
    for _ in range(n)
]

# 꼭지점 좌표 입력
for _ in range(k):
    sy, sx, ey, ex = map(int, input().split())
    # 직사각형 그려주기
    for i in range(sx, ex):
        for j in range(sy, ey):
            grid[i][j] = 1

# 함수들
# in_range(x, y)
def in_range(x, y):
    return 0 <= x and x < n and 0 <= y and y < m

# is_connected(x, y)
def is_connected(x, y):
    # 범위 내에 있고, 직사각형 아니고, 방문한 적 없으면 가능
    return in_range(x, y) and not grid[x][y] and not visited[x][y]

# dfs(x, y)
def dfs(x, y):

    global curr_area

    dxs, dys = [-1, 1, 0, 0], [0, 0, -1, 1]
    for dx, dy in zip(dxs, dys):
        nx, ny = x + dx, y + dy
        # 연결되어있으면,
        if is_connected(nx, ny):
            # 현재 영역 크기 하나 올려주고
            curr_area += 1
            # 방문 처리 해 주고
            visited[nx][ny] = 1
            # dfs 호출
            dfs(nx, ny)

# 설계
# visited
visited = [
    [0] * m
    for _ in range(n)
]

# 영역 갯수
area_num = 0

# dfs결과 영역의 크기 담아 줄 배열
area_list = []

# 최대 리커전 가능 횟수 올려주기
import sys
sys.setrecursionlimit(15000)

# grid 돌면서
for i in range(n):
    for j in range(m):
        # 비어있고, 방문한 적 없는 칸을 만나면,
        if not grid[i][j] and not visited[i][j]:
            # 현재 영역의 크기
            curr_area = 1
            # 영역 갯수 올려주고
            area_num += 1
            # 방문 처리 해 주고,
            visited[i][j] = 1
            # dfs 돌려주고,
            dfs(i, j)
            # 영역 크기 추가
            area_list.append(curr_area)

# area_list 정렬
area_list.sort()

# 출력
print(area_num)
for area in area_list:
    print(area, end=' ')