사용한 것
- 빈 영역의 개수, 빈 영역 하나당 크기를 구하기 위한 BFS
풀이 방법
- 2차원
visited
배열을 만들어 입력 받은 사각형에 포함되는 영역을 true로 만든다.
- 입력이 끝나면
visited
에 대해 2중 for문을 돌며 빈 영역(false)을 발견하면 numOfEmptyAreas
을 증가시키고 BFS 돈다.
- BFS 돌면서 방문한 좌표들의
visited
를 true로 바꾸고 sizeOfEmptyArea
를 증가시킨다.
- BFS 끝나면
sizesOfEmptyAreas
에 빈 영역의 크기인 sizeOfEmptyArea
를 넣는다.
- 빈 영역의 크기들을 오름차순해서 출력해야하므로
sizesOfEmptyAreas
을 sort()
한다.
코드
public class Main {
private static int[] dx = {-1, 0, 1, 0};
private static int[] dy = {0, 1, 0, -1};
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] splitLine = br.readLine().split(" ");
int m = Integer.parseInt(splitLine[0]);
int n = Integer.parseInt(splitLine[1]);
int k = Integer.parseInt(splitLine[2]);
boolean[][] visited = new boolean[n][m];
for (int i = 0; i < k; i++) {
splitLine = br.readLine().split(" ");
int x1 = Integer.parseInt(splitLine[0]);
int y1 = Integer.parseInt(splitLine[1]);
int x2 = Integer.parseInt(splitLine[2]);
int y2 = Integer.parseInt(splitLine[3]);
for (int x = x1; x < x2; x++) {
for (int y = y1; y < y2; y++) {
visited[x][y] = true;
}
}
}
int numOfEmptyAreas = 0;
List<Integer> sizesOfEmptyAreas = new ArrayList<>();
for (int x = 0; x < n; x++) {
for (int y = 0; y < m; y++) {
if (visited[x][y]) {
continue;
}
numOfEmptyAreas++;
Queue<int[]> q = new LinkedList<>();
q.offer(new int[]{x, y});
visited[x][y] = true;
int sizeOfEmptyArea = 0;
while (!q.isEmpty()) {
sizeOfEmptyArea++;
int[] cp = q.poll();
int cx = cp[0];
int cy = cp[1];
for (int i = 0; i < 4; i++) {
int nx = cx + dx[i];
int ny = cy + dy[i];
if (nx < 0 || nx >= n || ny < 0 || ny >= m || visited[nx][ny]) {
continue;
}
q.offer(new int[]{nx, ny});
visited[nx][ny] = true;
}
}
sizesOfEmptyAreas.add(sizeOfEmptyArea);
}
}
Collections.sort(sizesOfEmptyAreas);
StringBuilder sb = new StringBuilder();
for (int sizeOfEmptyArea : sizesOfEmptyAreas) {
sb.append(sizeOfEmptyArea).append(" ");
}
System.out.println(numOfEmptyAreas);
System.out.println(sb);
}
}