728x90
반응형
import sys
sys.setrecursionlimit(10000000)
m, n, k = map(int, input().split()) # 세로 가로 직사각형 수
# 직사각형으로 채워지면 1, 안 채워지면 0
graph = [ [0]*n for _ in range(m) ]
for i in range(k):
s1, e1, s2, e2 = map(int,sys.stdin.readline().split())
for x in range(s1,s2):
for y in range(e1, e2):
graph[y][x] = 1
def dfs ( x, y, cnt ):
graph[y][x] = 1
cnt += 1
move_x = [-1,1,0,0] # 가로 -> n
move_y = [0,0,-1,1] # 세로 -> m
for i in range(4):
nx = x + move_x[i]
ny = y + move_y[i]
if nx < 0 or ny < 0 or nx >=n or ny>=m :
continue
if not graph[ny][nx] :
cnt = dfs(nx,ny,cnt)
return cnt
area = []
for x in range(n):
for y in range(m):
if not graph[y][x]:
cnt = 0
area.append(dfs(x,y,cnt))
print( len(area) )
area.sort()
for i in range(len(area)):
print(area[i], end=' ')
step 1 ) 런타임 에러 방지를 위해 sys import 하고 graph 선언
직사각형으로 채워질 부분은 1, 채워지지 않은 부분은 0 으로 설정한다.
step 2 ) 직사각형의 좌표값을 입력받아 graph 채우기 -> 실제로 출력해보면 거꾸로 나오긴하는데 상관 없음
step 3 ) dfs 구현, 가로 세로로 움직이면서 연결된 영역 세기
각 영역별 넓이를 구해야 하므로 dfs 가 진행 될 때마다 cnt 를 세어주고 return 하는 식으로 계산한다.
step 4 ) graph 전체를 탐색하면서 dfs 를 진행한다. 이 때 돌려 받은 cnt 의 값을 각 구역의 넓이를 저장하는 area에 저장
step 5 ) area 의 길이와, 정렬한 결과를 출력
728x90
반응형
'백준 > DFS_BFS' 카테고리의 다른 글
# 11725 트리의 부모 찾기 파이썬 (0) | 2021.03.11 |
---|---|
# 2644 촌수계산 (0) | 2021.03.11 |
# 2468번: 안전 영역 (0) | 2020.10.12 |
# 4963번: 섬의 개수 (0) | 2020.10.12 |
# 11724번: 연결 요소의 개수 (0) | 2020.10.12 |