문제
M × N 크기의 모눈종이에 K개의 직사각형이 그려져 있을 때, 직사각형들로 인해 분리된 각 흰색 영역의 개수와 각 영역의 넓이를 오름차순으로 출력하는 문제이다. 좌표계는 좌하단이 원점이며, 직사각형은 격자 단위로 표현된다.
입력
첫째 줄에 M, N, K가 주어진다. (1 ≤ M, N ≤ 100, 1 ≤ K ≤ 100)
이후 K개의 줄에 직사각형의 좌하단 좌표 (x1, y1)과 우상단 좌표 (x2, y2)가 주어진다.
출력
첫째 줄에 분리된 영역의 개수를 출력한다. 둘째 줄에 각 영역의 넓이를 오름차순으로 공백으로 구분하여 출력한다.
예제
| 입력 | 출력 |
|---|---|
5 7 3 0 2 4 4 1 1 2 5 4 0 6 2 | 3 1 7 13 |
풀이
직사각형이 차지하는 격자 칸을 true로 표시한 뒤, 방문하지 않은 false 칸에서 BFS를 수행하여 연결된 영역의 넓이를 측정한다. 각 BFS 호출이 하나의 분리된 영역에 해당한다.
- M × N 크기의
boolean[][] map을 선언한다. 직사각형 좌표(x1, y1)-(x2, y2)를 받아 해당 격자 칸을true(장애물)로 설정한다. - 전체 격자를 순회하며
map[i][j] == false인 칸에서bfs(i, j)를 호출한다. - BFS에서는 현재 칸을
true로 표시하고 큐에 삽입한다. 상하좌우 인접 칸 중false인 칸을 모두 큐에 추가하며 방문 처리한다. - BFS가 종료될 때 카운트한 칸 수(
cnt)가 해당 영역의 넓이이다.ans리스트에 저장한다. - 모든 탐색 후
ans를 정렬하고 영역 수와 각 넓이를 출력한다.
핵심 아이디어: 플러드 필(Flood Fill) 기법으로 연결 요소를 분류한다. 방문 배열을 별도로 두지 않고 map 자체를 true로 갱신하여 재방문을 방지한다. BFS는 최단 거리 보장이 필요 없으므로 DFS로 대체해도 동일하게 동작한다.
코드
package com.ssafy.an.day099;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.StringTokenizer;
public class Day58BOJ2583영역구하기DFS { // 2583 영역구하기 DFS
static class Pos {
int r, c, d;
Pos(int r, int c, int d) {
this.r = r;
this.c = c;
this.d = d;
}
}
static int N, M, K;
static int[] dr = { -1, 1, 0, 0 }, dc = { 0, 0, -1, 1 };
static List<Integer> ans;
static Queue<Pos> q;
static boolean[][] map;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
StringBuilder sb = new StringBuilder();
M = Integer.parseInt(st.nextToken());
N = Integer.parseInt(st.nextToken()); // 순서
K = Integer.parseInt(st.nextToken());
ans = new ArrayList<>();
map = new boolean[N ][M ];
for (int k = 0; k < K; k++) {
st = new StringTokenizer(br.readLine());
int r1 = Integer.parseInt(st.nextToken());
int c1 = Integer.parseInt(st.nextToken());
int r2 = Integer.parseInt(st.nextToken());
int c2 = Integer.parseInt(st.nextToken());
for (int i = r1; i < r2; i++) {
for (int j = c1; j < c2; j++) {
map[i][j] = true;
}
}
}
for (int i = 0; i < map.length; i++) {
for (int j = 0; j < map[i].length; j++) {
if (!map[i][j])
bfs(i, j);
}
}
Collections.sort(ans);
sb.append(ans.size()).append("\n");
for (int a : ans) {
sb.append(a).append(" ");
}
System.out.println(sb);
br.close();
}
private static void bfs(int idx, int jdx) {
q = new LinkedList<>();
q.add(new Pos(idx, jdx, 0));
map[idx][jdx] = true;
int cnt = 0;
while (!q.isEmpty()) {
Pos p = q.poll();
cnt++;
for (int i = 0; i < 4; i++) {
int nr = p.r + dr[i];
int nc = p.c + dc[i];
if (nr < 0 || nr >= map.length || nc < 0 || nc >= map[0].length)
continue;
if (!map[nr][nc]) {
map[nr][nc] = true;
q.add(new Pos(nr, nc, p.d));
}
}
}
ans.add(cnt);
}
}복잡도
- 시간: O(N * M) — 전체 격자 칸을 최대 한 번씩 방문
- 공간: O(N * M) — 방문 배열(map) 및 BFS 큐