[백준 02583] 영역 구하기 [Java]

문제

https://www.acmicpc.net/problem/2583

---

풀이

K개의 직사각형을 제외한 나머지 영역의 개수와 넓이를 구하는 문제다.

우선 문제의 예제를 살펴보자.

K개의 직사각형에 대해 표시하면 다음과 같다. 

왼쪽아래 좌표와 오른쪽위 좌표가 주어지는데 그림을 회전시켜보자.

일반적인 배열의 논리적 표현과 같다.

그러면 사각형의 넓이는 어떻게 구할까?

전체적으로 행과 열을 축소시키면 된다.

즉, 이 문제에서 다룰 범위는 M, N에 대해 (0, 0) ~ (N - 1, M - 1)가 된다.

K개의 좌표를 입력받아 블럭표시를 해주자.

이제 블럭( BLCOK )이 아니고, 방문한적 없는( EMPTY )영역들에 대해 BFS를 진행하면된다.

bfs(i, j)는(i, j)에서 bfs를 하고, 하나로 연결된 영역의 넓이를 반환한다.

영역의 수는 bfs가 끝나고, main에서 카운트해주면 된다.

마지막으로 문제의 조건대로 영역의 넓이를 오름차순으로 정렬하고, 영역의 수와 넓이들을 출력하면 된다.

---

소스코드

보기