📍 문제 설명
💡 접근
영역에 맞게 직사각형을 그리고나서 분리된 영역의 갯수와 넓이를 구하면 되는 문제였다.
👩💻 코드
import java.util.*;
public class Main {
static int n, m, k, answer, area;
static int[][] board,dis,ch;
static int[] dx = {-1,1,0,0};
static int[] dy = {0,0,-1,1};
static int[] combi;
public static void main(String[] args) {
Main T = new Main();
Scanner kb = new Scanner(System.in);
m = kb.nextInt();
n = kb.nextInt();
k = kb.nextInt();
board = new int[m][n];
//0,2 -> 2행 0열 4,0 -> 0행 4열
for(int i = 0; i < k; i++) {
int leftDownX = kb.nextInt(); //행
int leftDownY = kb.nextInt(); //열
int rightUpX = kb.nextInt(); //행
int rightUpY = kb.nextInt(); //열
for(int j = leftDownY; j < rightUpY; j++) {
for(int k = leftDownX; k < rightUpX; k++) {
board[j][k] = 1;
}
}
}
//각 영역에 넓이 담기
ArrayList<Integer> list = new ArrayList<>();
//이제 0인 부분을 탐색하여 각 영역의 넓이를 탐색
for(int i = 0; i < m; i++) {
for(int j = 0; j < n; j++) {
area = 0;
if(board[i][j] == 0) {
answer++;
area++;
board[i][j] = 1;
T.solution(i, j);
list.add(area);
}
}
}
Collections.sort(list);
System.out.println(answer);
for(int x : list) System.out.print(x + " ");
}
private void solution(int x, int y) {
//상하좌우를 확인하여 빈 영역이면 answer 증가 및 눈금채우기
for(int i = 0; i < 4; i++) {
int nx = x + dx[i];
int ny = y + dy[i];
if(nx>=0 && ny>=0 && nx<m && ny<n && board[nx][ny] == 0) {
area++;
board[nx][ny] = 1;
solution(nx, ny);
}
}
}
}