[Graph] 2583번 - 영역 구하기(44일차)

#코드 실행 시간 단축
import sys
input = sys.stdin.readline

#세로 길이, 가로 길이, 직사각형 개수
M, N, K = map(int, input().split())
#직사각형 색칠 그래프
graph = [[0 for _ in range(N)] for _ in range(M)]
#방문기록
visit = [[0 for _ in range(N)] for _ in range(M)]
#분리된 영역 크기 저장 list
k_cnt = []

#dfs 탐색 함수
def dfs(graph, y_root, x_root):
  #분리된 영역의 크기 변수
  cnt = 0
  #탐색 위치 저장 스택
  stack = [[y_root, x_root]]

  #탐색 y좌표, x좌표
  y = [-1, 1, 0, 0]
  x = [0, 0, -1, 1]

  #탐색 위치가 있는 동안 반복
  while(stack):
    #탐색 위치 확인
    index = stack.pop()
    #방문기록 설정
    visit[index[0]][index[1]] = 1
    #분리된 영역 크기 추가
    cnt += 1
    #상하좌우로 탐색하며 탐색 위치 추가
    for i in range(4):
      ny = index[0] + y[i]
      nx = index[1] + x[i]
      #새로운 탐색 위치가 범위 내에 있고, 탐색 대상이며, 방문기록이 없을 때
      if(0 <= ny < M and 0 <= nx < N):
        if(graph[ny][nx] == 0 and visit[ny][nx] == 0):
          stack.append([ny, nx])
  #분리된 영역의 크기 반환
  return cnt

#직사각형 색칠
for i in range(K):
  x1, y1, x2, y2 = map(int, input().split())
  for y in range(y1, y2):
    for x in range(x1, x2):
      graph[y][x] = 1

#전 그래프에 대해 탐색
for i in range(M):
  for j in range(N):
    if(graph[i][j] == 0 and visit[i][j] == 0):
      #분리된 영역의 크기를 list에 추가
      k_cnt.append(dfs(graph, i, j))

#분리된 영역의 개수와 정렬된 크기를 출력
print(len(k_cnt))
print(*sorted(k_cnt))

#인사이트
#dfs, bfs 풀이 방법은 빠르게 떠올리지만 구현 속도가 느림
#손에 익을 만큼 익숙해질 필요가 있음
#메모리와 속도를 줄일 수 있는 로직와 변수 활용 필요