[백준] 2583 - 영역 구하기 (Java)

Problem

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

MxN 크기의 모눈종이 위에 주어진 좌표의 K개의 직사각형을 그린다.
그 K개의 직사각형의 내부를 제외한 나머지 부분의 각 영역의 넓이를 구한다.
각 영역의 넓이를 오름차순으로 정렬하여 출력한다.

①면적 -> 1
②면적 -> 7
③면적 -> 13

Approach & Logic

(1) MxN 크기의 모눈종이 위에 주어진 좌표의 K개의 직사각형을 그린다.
-> 사각형 영역에 해당하는 배열에 1 넣기

(2) 그 K개의 직사각형의 내부를 제외한 나머지 부분의 각 영역의 넓이를 구한다.
-> BFS함수를 사용하여 현재 좌표의 상하좌우로 움직여 '직사각형 내부인지' or '방문한적 있는지'를 확인하여 BFS를 다시 부르는 형식

(3) 각 영역의 넓이를 오름차순으로 정렬하여 출력한다.
-> 영역의 넓이를 구할 때마다 ArrayList에 넣고 마지막에 list를 정렬한 후 StringBuilder에 넣어 출력

---

Java 2차원배열

문제에서 모눈종이는 왼쪽 아래가 (0, 0) 이지만
Java에서 2차원배열은 왼쪽 위가 [0][0]이기 때문에

//그래프에 표시하기
for(int x=x1; x<x2; x++) {
	for(int y=y1; y<y2; y++) {
    	graph[y][x] = 1; //어레이는 왼쪽 위에서 시작하기 때문에
    }
}

다음과 같이 2차원배열인 graph에 표시할때
graph[x][y]가 아니라 graph[y][x]로 해야 한다.

Code

package BaekJoon_java;

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

public class boj_2583 {
    static int m;
    static int n;
    static int k;

    static int[][] graph;
    static boolean[][] visited;

    static int[] dx = {0,1,0,-1};
    static int[] dy = {1,0,-1,0};
    
    
    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer str = new StringTokenizer(br.readLine());
        m = Integer.parseInt(str.nextToken()); //5
        n = Integer.parseInt(str.nextToken()); //7 
        k = Integer.parseInt(str.nextToken()); //3

        graph = new int[m][n];
        visited = new boolean[m][n];
        
        ArrayList<Integer> list = new ArrayList<Integer>();

        for(int i=0; i<k; i++) {
            str = new StringTokenizer(br.readLine());
            int x1 = Integer.parseInt(str.nextToken()); //0
            int y1 = Integer.parseInt(str.nextToken()); //2
            int x2 = Integer.parseInt(str.nextToken()); //4
            int y2 = Integer.parseInt(str.nextToken()); //4

            //그래프에 표시하기
            for(int x=x1; x<x2; x++) {
                for(int y=y1; y<y2; y++) {
                    graph[y][x] = 1; //어레이는 왼쪽 위에서 시작하기 때문에
                }
            }
        }

        // bfs를 이용하여 면적 구하기
        for(int i=0; i<m; i++) {
            for(int j=0; j<n; j++) {
                if(!visited[i][j] && graph[i][j]==0) { //방문한적 없고 직사각형 내부 좌표가 아닐때
                    int data = bfs(i, j); //해당 좌표 bfs함수로 보내기
                    list.add(data); //list에 면적의 넓이 넣기
                }
            }
        }

        //결과 출력
        StringBuilder sb = new StringBuilder();
        Collections.sort(list); //list를 오름차순으로 sort하기
        sb.append(list.size() + "\n");
        for (int i = 0; i < list.size(); i++) {
            sb.append(list.get(i) + " ");
        }
        System.out.print(sb);
    }

    //BFS 함수
    public static int bfs(int x, int y) {
        Queue<int[]> q = new LinkedList<>();
        q.offer(new int[] {x, y});
        visited[x][y] = true;
        int cnt = 1;

        while(!q.isEmpty()) {
            int[] curData = q.poll();
            int curX = curData[0];
            int curY = curData[1];

            for(int i=0; i<4; i++){
                //현재 좌표에서 상우하좌로 움직여 다음 좌표 구하기
                // dx = {0,1,0,-1}  
                // dy = {1,0,-1,0}
                int nextX = curX + dx[i]; //다음 x좌표
                int nextY = curY + dy[i]; //다음 y좌표

                if(0<=nextX && nextX<m && 0<=nextY && nextY<n) {
                    //방문한적 없고 직사각형 내부 좌표가 아닐때
                    if(!visited[nextX][nextY] && graph[nextX][nextY]==0) { 
                        visited[nextX][nextY] = true;
                        q.offer(new int[] {nextX, nextY}); //큐에 다음좌표를 넣어서 다음 while문에서 그 좌표를 확인할 수 있게 함 (재귀)
                        cnt++; //면적 +1 해주기
                    }
                }
            }
        }

        return cnt;
    }
}