[백준 2583번] 영역 구하기 python

- 문제 유형 : 그래프 탐색

- 간단한 문제라는데 또 헤맸다.

bfs, dfs를 어떤 부분에서 써야할지 감이 안왔다.

dfs를 쓰기 위해 재귀의 깊이를 setrecursionlimt를 써서 정해주었다.

구간의 칸 개수를 세기 위해 위, 아래, 왼쪽, 오른쪽을 체크할 수 있는 dx, dy를 만들었다.

dfs에서 개수를 세서 구간별로 저장시키는 방법을 찾는 게 어려웠다..

 

 

[코드 구현]

import sys

sys.setrecursionlimit(10000)

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

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

for _ in range(K):

    x1, y1, x2, y2 = map(int, input().split())

   

    for i in range(x1, x2):

        for j in range(y1, y2):

            graph[j][i] = 1

# print(graph)

dx = [0, 0, 1, -1]

dy = [1,-1, 0, 0]

def dfs(x, y, count) :

    graph[y][x] = 1

    for p in range(4) :

        nx = x + dx[p]

        ny = y + dy[p]

        if 0 <= nx < N and 0<= ny < M and graph[ny][nx] == 0 :

            count = dfs(nx, ny, count + 1)

    return count

result = []

for ny in range(M):

    for nx in range(N) :

        if graph[ny][nx] == 0:

            result.append(dfs(nx, ny, 1))

print(len(result))

print(*sorted(result))