백준 2583번 영역 구하기 (Java, BFS)

문제 요약

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

도화지의 크기와 그 위에 그려진 K개의 직사각형이 주어질 때 직사각형을 제외한 나머지 빈 영역의 개수와 각 영역의 넓이를 구하는 문제입니다.

• 도화지는 M × N 크기의 2차원 배열로 표현됩니다.
• 좌표는 (x1, y1) ~ (x2, y2) 형태로 주어지며, 왼쪽 아래가 시작점, 오른쪽 위가 끝점입니다.
• 직사각형이 채워진 영역은 1로 표시하고, 나머지 빈 영역은 0입니다.
• 0인 영역끼리 인접한 곳을 하나의 영역으로 간주합니다.
  (상하좌우 연결된 경우만 인접)

출력:

• 빈 영역의 개수
• 각 영역의 넓이 (오름차순)

---

전체 코드

import java.util.*;

class Point {
	public int x, y;
	
	Point(int x, int y) {
		this.x = x;
		this.y = y;
	}
}
public class Main {
	static int[] dx = {-1, 0, 1, 0};
	static int[] dy = {0, 1, 0, -1};
	static int n, m;
	
	public void BFS(int[][] arr) {
		Queue<Point> q = new LinkedList<>(); 
		int count = 0;
		ArrayList<Integer> answer = new ArrayList<>();
		
		for(int x=0; x<n; x++) {
			for(int y=0; y<m; y++) {
				if(arr[x][y]==0) {
					arr[x][y] = 1;
					count++;
					int area = 1;
					q.offer(new Point(x, y));
					while(!q.isEmpty()) {
						Point tmp = q.poll();
						for(int i=0; i<4; i++) {
							int nx = tmp.x + dx[i];
							int ny = tmp.y + dy[i];
							if(nx>=0 && nx<n && ny>=0 && ny<m && arr[nx][ny]==0) {
								arr[nx][ny] = 1;
								q.offer(new Point(nx, ny));
								area++;
							}
						}
					}
					answer.add(area);
				}
			}
		}
		System.out.println(count);
		Collections.sort(answer);
		for(int i=0; i<answer.size(); i++) System.out.print(answer.get(i)+" ");
	}
	
	public static void main(String[] args) {
		Main T = new Main();
		Scanner sc = new Scanner(System.in);
		n = sc.nextInt();
		m = sc.nextInt();
		int[][] arr = new int[n][m];
		int k = sc.nextInt();
		for(int i=0; i<k; i++) {
			int lx = sc.nextInt();
			int ly = sc.nextInt();
			int rx = sc.nextInt();
			int ry = sc.nextInt();
			for(int row=ly; row<ry; row++) {
				for(int col=lx; col<rx; col++) {
					arr[row][col] = 1;
				}
			}
		}
		T.BFS(arr);
		sc.close();
	}
}

---

코드 설명

static int[] dx = {-1, 0, 1, 0};
static int[] dy = {0, 1, 0, -1};

• 4방향 이동을 위한 배열 (상, 우, 하, 좌)

for (int row = ly; row < ry; row++) {
    for (int col = lx; col < rx; col++) {
        arr[row][col] = 1;
    }
}

• 입력된 직사각형 영역을 1로 채움
• y좌표가 행(row), x좌표가 열(col)과 매핑됨에 주의

if (arr[x][y] == 0) {
    arr[x][y] = 1;
    count++;
    int area = 1;
    q.offer(new Point(x, y));

• 0인 좌표에서 BFS 시작
• 시작 지점을 1로 바꿔 방문 체크 후 큐에 삽입
• area는 현재 영역의 넓이

while (!q.isEmpty()) {
    Point tmp = q.poll();
    for (int i = 0; i < 4; i++) {
        int nx = tmp.x + dx[i];
        int ny = tmp.y + dy[i];
        if (nx >= 0 && nx < n && ny >= 0 && ny < m && arr[nx][ny] == 0) {
            arr[nx][ny] = 1; // 방문 체크
            q.offer(new Point(nx, ny));
            area++;
        }
    }
}

• BFS로 상하좌우 인접한 0인 곳을 계속 방문
• 방문 시마다 넓이 +1, 그리고 방문 체크

Collections.sort(answer);
System.out.println(count);
for (int a : answer) System.out.print(a + " ");

• 넓이 리스트 정렬 후 출력

---

시간 복잡도 분석

• 직사각형 채우기 : O(K × 면적) 
• BFS 탐색 : O(N × M)
• 전체 반복문 : O(N × M)
• 정렬 : O(A log A) (A = 영역 수 ≤ N×M)
• 총 시간 복잡도: O(N × M + A log A)