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

+ Recent posts