[백준]2583번. 영역 구하기(JAVA)

https://to-travel-coding.tistory.com/110

---

풀이

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

class Main {

    static int[][] arr;
    static boolean[][] visited;
    static int answer;
    static int m;
    static int n;
    static Queue<int[]> q = new LinkedList<>();
    static int[] dx = {0, 0, -1, 1};
    static int[] dy = {1, -1, 0, 0}; // 북, 남, 서, 동 탐색

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        st = new StringTokenizer(br.readLine());

        m = Integer.parseInt(st.nextToken());
        n = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(st.nextToken());

        arr = new int[m][n];
        visited = new boolean[m][n];

        ArrayList<Integer> answerArr = new ArrayList<>();

        for(int i = 0; i < k; i++){
            st = new StringTokenizer(br.readLine());
            int leftUnderY = Integer.parseInt(st.nextToken());
            int leftUnderX = Integer.parseInt(st.nextToken());
            int rightTopY = Integer.parseInt(st.nextToken());
            int rightTopX = Integer.parseInt(st.nextToken());

            for(int j = leftUnderX; j < rightTopX; j++){
                for(int t = leftUnderY; t < rightTopY; t++){
                    arr[j][t] = 1;
                }
            }
        }


        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                if(!visited[i][j] && arr[i][j] == 0){
                    answer = 0;
                    bfs(i,j);
                    answerArr.add(answer);
                }
            }
        }

        Collections.sort(answerArr);

        System.out.println(answerArr.size());

        for(int x : answerArr){
            System.out.print(x + " ");
        }




    }

    public static void bfs(int x, int y) {
        q.offer(new int[]{x, y}); // 큐에 요소를 추가합니다.
        answer++;
        visited[x][y] = true;

        while(!q.isEmpty()){
            int[] temp = q.poll();
            int startX = temp[0];
            int startY = temp[1];

            for(int i = 0; i < 4; i++){
                int nowX = startX + dx[i];
                int nowY = startY + dy[i];

                if(nowX >= 0 && nowX < m && nowY >= 0 && nowY < n && arr[nowX][nowY] == 0 && !visited[nowX][nowY]){
                    visited[nowX][nowY] = true;
                    answer++;
                    q.offer(new int[]{nowX, nowY});

                }
            }
        }
    }

}

 

bfs를 이용하기 위해 처리를 해두고 사방탐색을 이용하는 제일 대표적인 문제이다. 다만 주의할 점은 x,y의 좌표가 조금씩 뒤바뀌어 있다는 부분이다. 행 열을 이용하는 것은 일반적인 x,y의 좌표와 반대되는 자리이기 때문이다.

 

따라서 문제를 풀면서 사용자 입력을 통해 사각형의 위치를 체크하는 부분에만 신경을 써서 체크하고, 실제로 영역의 넓이를 구할 때는 어차피 오름차순으로 출력한다는 점을 이용하여 일반적인 행열의 bfs와 동일하게 구했다.