[BaekJoon] 2583 영역 구하기

1.  문제 링크

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

2.  문제

요약

• 눈금의 간격이 1인 M X N 크기의 모눈종이가 있고 해당 모눈종이 위에 K개의 직사각형을 그립니다.
• K개의 직사각형의 내부를 제외한 나머지 부분이 분리된 영역들로 나누어지는데 K개의 직사각형의 좌표가 주어질 때, K개의 직사각형 내부를 제외한 나머지 부분이 몇 개의 분리된 영역으로 나누어지고, 분리된 각 영역의 넓이가 얼마인지 구하는 문제입니다.
• 입력: 첫 번째 줄에 100보다 작거나 같은 자연수 M, N과 100보다 작거나 같은 자연수인 직사각형의 개수 K가 주어지고 두 번째 줄부터 K개의 줄에는 한 줄에 하나씩 직사각형의 왼쪽 아래 꼭짓점 x, y 좌표값과 오른쪽 위 꼭짓점의 x, y 좌표값이 주어집니다.
• 출력: 첫 번째 줄에 분리되어 나누어지는 영역의 개수를 출력하고 두 번째 줄에 각 영역의 넓이를 오름차순으로 출력합니다.

3.  소스코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;

public class Main {
	static int row, col;
	static int[][] square;
	static int count = 0;
	static int[] result;
	boolean[][] visited;
	public void dfs(int x, int y) {
		int[] dx = {-1, 0, 1, 0};
		int[] dy = {0, -1, 0, 1};
		visited[x][y] = true;
		result[count]++;
		for(int i = 0; i < 4; i++) {
			int cx = x + dx[i];
			int cy = y + dy[i];
			if(cx >= 0 && cx < row && cy >= 0 && cy < col) {
				if(!visited[cx][cy] && square[cx][cy] == 0) {
					dfs(cx, cy);
				}
			}
		}
	}
	
	public int[] getNumOfArea() {
		result = new int[row * col + 1];
		visited = new boolean[row][col];
		for(int i = 0; i < row; i++) {
			for(int j = 0; j < col; j++) {
				if(!visited[i][j] && square[i][j] == 0) {
					count++;
					dfs(i, j);
				}
			}
		}
		int[] area = new int[count];
		for(int i = 1; i <= count; i++) {
			area[i - 1] = result[i];
		}
		Arrays.sort(area);
		return area;
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		String[] input = br.readLine().split(" ");
		row = Integer.parseInt(input[0]);
		col = Integer.parseInt(input[1]);
		int k = Integer.parseInt(input[2]);
		square = new int[row][col];
		for(int i = 0; i < k; i++) {
			input = br.readLine().split(" ");
			int y1 = Integer.parseInt(input[0]);
			int x1 = Integer.parseInt(input[1]);
			int y2 = Integer.parseInt(input[2]) - 1;
			int x2 = Integer.parseInt(input[3]) - 1;
			for(int j = x1; j <= x2; j++) {
				for(int l = y1; l <= y2; l++) {
					square[j][l] = 1;
				}
			}
		}
		br.close();
		Main m = new Main();
		int[] area = m.getNumOfArea();
		bw.write(count + "\n");
		for(int i = 0; i < count; i++) {
			bw.write(area[i] + " ");
		}
		bw.flush();
		bw.close();
	}
}

4.  접근

• 해당 문제는 DFS를 이용하여 해결할 수 있습니다.
• 모눈종이의 모든 칸들을 확인하면서 분리되어 나누어지는 영역을 구하고 해당 영역의 넓이를 구해나갑니다.
• 모눈종이의 각 칸을 방문했는지 확인하기 위한 boolean 타입의 2차원 배열 visited를 생성하고 분리되어 나누어지는 영역의 개수를 나타내는 count라는 변수를 하나 생성하고 0으로 초기화하며 각 영역의 넓이를 나타내는 1차원 배열 result를 생성합니다.
• 모눈종이의 모든 칸들을 돌면서 아직 해당 칸을 방문하지 않았고 해당 위치가 직사각형의 내부가 아니라면 분리되어 나누어지는 영역의 개수를 1 증가시키고 해당 위치의 상하좌우를 확인하여 분리되어 나누어지는 영역의 넓이를 확인합니다.

1. 모눈종이를 나타내는 2차원 배열 square를 생성하고 직사각형의 좌표들을 입력받아 직사각형 내부에 해당하는 위치의 값을 1로 변경합니다.
2. 분리되어 나누어지는 영역의 넓이를 나타내는 1차원 배열 result와 모눈종이 각 위치를 방문하였는지를 나타내는 2차원 배열 visited를 생성합니다.
3. 모눈종이의 각 위치를 돌면서 분리되어 나누어지는 영역의 개수와 각 영역의 넓이를 구합니다.
   1. 해당 위치를 아직 방문하지 않았고 모눈종이에서 해당 위치의 값이 0, 즉 직사각형 내부가 아니라면 분리되어 나누어지는 영역의 개수를 1 증가시키고 해당 영역의 넓이를 구합니다.
      1. 상하좌우를 나타낼 dx, dy 배열을 생성하고 값을 설정하며 해당 위치를 방문했다는 의미로 해당 위치의 visited 값을 true로 변경합니다. 또한 해당 분리되어 나누어지는 영역의 넓이를 1 증가시킵니다.
      2. 해당 위치의 상하좌우를 방문하여 해당 위치가 M X N 2차원 배열 내에 있고 아직 방문되지 않았으며 해당 위치의 값이 0이라면, 즉 직사각형 내부가 아니라면 해당 위치에서 다시 상하좌우를 확인하여 분리되어 나누어지는 영역의 넓이를 구합니다.
4. 3번 과정 반복문을 통해 구한 분리되어 나누어지는 영역의 넓이들을 오름차순으로 정렬합니다.
5. count 변수의 값, 즉 분리되어 나누어지는 영역의 개수 및 분리되어 나누어지는 영역의 넓이들을 오름차순으로 출력합니다.