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

문제 링크

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

문제 풀이

기본적인 bfs 문제였다 다만 영역을 설정할때 문제에서는 (0,0)이 좌측 하단에 있고,
(m,n)값이 우측 상단에 있는데 이를 위아래로 대칭이동 시켜 2차원 배열에서처럼
(0,0)을 좌측 상당, (m,n)을 우측 하단으로 이동시켰다는 가정하에 면적을 구했다.
그려지는 사각형의 위치도 대칭으로 바뀌기만 할뿐 만드는 넓이, 겹치는부분은 똑같기 때문에 상관없다.

코드

import java.util.*;

public class Main {

    static int m;
    static int n;
    static int[][] map;
    static boolean[][] chk;
    static int[] diry = {-1, 0, 1, 0};
    static int[] dirx = {0, 1, 0, -1};

    static class Node {
        int y;
        int x;

        public Node(int y, int x) {
            this.y = y;
            this.x = x;
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        m = sc.nextInt();
        n = sc.nextInt();
        int k = sc.nextInt();
        map = new int[m][n];
        chk = new boolean[m][n];
        List<Integer> list = new ArrayList<>();
        int answer = 0;
        for (int i = 0; i < k; i++) {
            //시작위치 [m][0]a
            int x1 = sc.nextInt();
            int y1 = sc.nextInt();

            int x2 = sc.nextInt();
            int y2 = sc.nextInt();
            //System.out.println((m-y2)+" "+(y2-y1));
            for (int y = y1; y < y2; y++) {
                for (int x = x1; x < x2; x++) {
                    map[y][x] = 1;
                }
            }
            //System.out.println(Arrays.deepToString(map));
        }
//        for(int i=0; i<m; i++){
//            System.out.println(Arrays.toString(map[i]));
//        }


        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (!chk[i][j] && map[i][j] == 0) {
                    answer++;
                    list.add(bfs(i, j));
                }
            }
        }
        System.out.println(answer);
        Collections.sort(list);
        String res = "";
        for(int i=0; i<list.size(); i++){
            res +=(list.get(i)+" ");
        }
        System.out.println(res.trim());

    }

    public static int bfs(int y, int x) {
        Queue<Node> queue = new LinkedList<>();
        int answer = 1;
        queue.add(new Node(y, x));
        chk[y][x] = true;
        while (!queue.isEmpty()) {
            Node now = queue.poll();
            for (int i = 0; i < 4; i++) {
                int now_y = now.y + diry[i];
                int now_x = now.x + dirx[i];
                if(now_y>=0 && now_y<m && now_x>=0 && now_x<n){
                    if(!chk[now_y][now_x] && map[now_y][now_x]==0){
                        queue.add(new Node(now_y,now_x));
                        chk[now_y][now_x] = true;
                        answer++;
                    }
                }

            }
        }


        return answer;
    }
}