그림판 조각 크기
면접 대비시간 제한2초메모리 제한128 MB
칸 사이를 막는 선분이 주어진 격자에서 BFS나 DFS로 연결된 영역들을 찾아 가장 큰 영역과 가장 작은 영역의 크기를 구합니다.
문제
직사각형 그림판에는 칸 사이의 경계 위에 그어진 선분들이 있다. 각 선분은 그림판의 변과 평행하며, 선분을 지나 서로 맞닿은 칸으로는 이동할 수 없다.
이 선분들 때문에 그림판은 하나 이상의 연결된 조각으로 나뉜다. 한 조각의 크기는 그 조각에 포함된 단위 칸의 개수이다.
그림판의 세로 크기와 가로 크기, 그리고 그려진 선분들이 주어질 때 가장 큰 조각의 크기와 가장 작은 조각의 크기를 구하시오.
입력
첫째 줄에 그림판의 세로 크기 N과 가로 크기 M이 공백으로 구분되어 주어진다. (1 <= N, M <= 500)
둘째 줄에 선분의 수 T가 주어진다. (1 <= T <= 1000)
다음 T개의 줄에는 네 정수 Sx Sy Ex Ey가 주어진다. 이는 점 (Sx, Sy)와 점 (Ex, Ey)를 잇는 선분이 존재한다는 뜻이다. 그림판의 왼쪽 위 꼭짓점은 (0, 0), 오른쪽 아래 꼭짓점은 (N, M)이다.
출력
첫째 줄에 가장 큰 조각의 크기를 출력한다.
둘째 줄에 가장 작은 조각의 크기를 출력한다.
힌트
각 단위 칸을 정점으로 보고, 선분이 지나가는 칸 사이의 인접 이동만 막으면 연결 요소의 크기를 탐색으로 구할 수 있다.