[BOJ2583] 영역 구하기

분리된 개수, 분리된 각 영역의 넓이가 얼마인지 구하기

• M, N (<= 100) 크기의 모눈종이
• K개의 직사각형 그린 후, 나머지는 몇 개의 분리된 영역으로 나뉨
• 직사각형 내부를 제외한 나머지 부분이 몇 개의 분리된 영역으로 나뉘는지
• 각 영역의 넓이가 얼마인지 구하기

입력

• M, N, K (<= 100)
• K개 줄에는 왼쪽아래 x, y 좌표, 오른쪽 위 x, y좌표
• 모눈종이 왼쪽아래가 0, 0 오른쪽 위가 N, M
• 직사각형이 모눈종이 전체 채우는 경우 없음

출력

• 첫째 줄 나누어지는 영역 개수
• 각 영역 넓이 오름차순으로

설계

• 클러스터를 구하는 문제
• dfs를 이용해 빈 영역만 서칭하는 알고리즘
• 좌표를 이용한 직사각형 설계가 중요
• 직사각형은 좌표를 x1 ~ x2, y1 ~ y2 까지 반복문 돌리면 됨

How I solved(click to github)

---

ref :
BOJ2583