백준 2583번: 영역 구하기

문제 설명

• https://www.acmicpc.net/problem/2583
• 색칠되지 않은 영역을 구하는 문제입니다.

접근법

• BFS로 정답을 구합니다.
• 도형을 90도 오른쪽으로 돌리면 평소 사용하던 좌표계와 동일해 집니다. 영역의 개수와 크기는 도형을 돌려도 변함이 없기 때문에 회전한 상태로 정답을 구했습니다.
  • 
  • 

정답

import java.util.*;
import java.io.*;

public class Main {
	static int[] dx = { 1, 0, -1, 0 };
	static int[] dy = { 0, -1, 0, 1 };
	static int M, N;
	static boolean[][] board;
	static List<Integer> lst = new LinkedList<Integer>();

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		M = Integer.parseInt(st.nextToken());
		N = Integer.parseInt(st.nextToken());
		int K = Integer.parseInt(st.nextToken());
		board = new boolean[N][M];
		for (int k = 0; k < K; k++) {
			st = new StringTokenizer(br.readLine());
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			int c = Integer.parseInt(st.nextToken());
			int d = Integer.parseInt(st.nextToken());
			for (int i = a; i < c; i++) {
				for (int j = b; j < d; j++) {
					board[i][j] = true;
				}
			}
		}
		int answer = 0;
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				if (!board[i][j]) {
					answer++;
					board[i][j] = true;
					lst.add(BFS(new int[] { i, j }));
				}
			}
		}

		Collections.sort(lst); // 오름차순 정렬
		System.out.println(answer);
		for (int i = 0; i < lst.size(); i++) {
			System.out.print(lst.get(i)+" ");
		}
	}

	public static int BFS(int[] start) {
		Queue<int[]> q = new LinkedList<int[]>();
		q.add(start);
		int cnt = 0;
		while (!q.isEmpty()) {
			cnt++;
			int[] now = q.poll();
			for (int d = 0; d < 4; d++) {
				int nx = dx[d] + now[0];
				int ny = dy[d] + now[1];
				if (0 <= nx && nx < N && 0 <= ny && ny < M && !board[nx][ny]) {
					board[nx][ny] = true;
					q.add(new int[] { nx, ny });
				}
			}

		}
		return cnt;
	}

}