백준 2583 영역 구하기

문제

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

---

입출력

---

예제

---

태그

• 그래프 이론
• 그래프 탐색
• 너비 우선 탐색
• 깊이 우선 탐색

---

풀이

• bfs
• 전체 map의 값을 0으로 놓고 직사각형으로 칠해져 있는 좌표들은 1로 설정한다.
• 전체 map을 이중 for문으로 돌면서 값이 0인 부분을 기준으로 bfs를 한다.
• 영역의 개수는 전체 map을 이중 for문으로 돌 때 bfs를 한 횟수이다.
• 영역의 넓이는 각각 bfs를 진행할 때 queue에 값을 넣는 횟수이다.(단, 1을 추가해줘야한다.)
• 오름차순으로 답을 구하기 위하여 ArrayList를 사용한다.

---

코드

정답 코드

/**
 * 2583_영역 구하기
 *
 * bfs
 * 전체 map의 값을 0으로 놓고 직사각형으로 칠해져 있는 좌표들은 1로 설정한다.
 * 전체 map을 이중 for문으로 돌면서 값이 0인 부분을 기준으로 bfs를 한다.
 * 영역의 개수는 전체 map을 이중 for문으로 돌 때 bfs를 한 횟수이다.
 * 영역의 넓이는 각각 bfs를 진행할 때 queue에 값을 넣는 횟수이다.(단, 1을 추가해줘야한다.)
 *
 * 오름차순으로 답을 구하기 위하여 ArrayList를 사용한다.
 */

public class P_2583 {
    static int M, N, K;
    static int[][] map; // 전체 M*N 좌표 맵
    static int[] mx = {-1, 1, 0, 0};
    static int[] my = {0, 0, -1, 1};
    static int cnt = 0; // 영역의 개수
    static ArrayList<Integer> list = new ArrayList<>(); // 영역의 넓이를 담을 arrayList

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

        M = Integer.parseInt(st.nextToken());
        N = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());

        map = new int[M][N];

        for (int i = 0; i < K; i++) {
            // 주어진 직사각형 좌표를 토대로 map의 값을 1로 설정
            st = new StringTokenizer(br.readLine());
            int x1 = Integer.parseInt(st.nextToken());
            int y1 = Integer.parseInt(st.nextToken());
            int x2 = Integer.parseInt(st.nextToken());
            int y2 = Integer.parseInt(st.nextToken());

            for (int x = x1; x < x2; x++) {
                for (int y = y1; y < y2; y++) {
                    map[y][x] = 1;
                }
            }
        }

        // 전체 map을 돌며 값이 0인 부분을 시작점으로 bfs
        for (int i = 0; i < map.length; i++) {
            for (int j = 0; j < map[i].length; j++) {
                if(map[i][j] == 0){
                    map[i][j] = 1;
                    bfs(i,j);
                    cnt++;
                }
            }
        }

        System.out.println(cnt);

        // 영역의 넓이를 오름차순
        Collections.sort(list);
        for (int i = 0; i < list.size(); i++) {
            System.out.printf(list.get(i) + " ");
        }

    }

    static void bfs(int y, int x) {
        int num = 0; // 영역의 넓이
        Queue<Point> queue = new LinkedList<>();
        queue.add(new Point(y,x));

        while (!queue.isEmpty()){
            Point p = queue.poll();

            for (int i = 0; i < 4; i++) {
                int dy = p.y + my[i];
                int dx = p.x + mx[i];

                if(0<=dx && dx<N && 0<=dy && dy<M){
                    if(map[dy][dx] == 0){
                        queue.add(new Point(dy, dx));
                        map[dy][dx] = 1;
                        num++;
                    }
                }
            }
        }
        // 초기 영역의 넓이를 0으로 설정해서 1을 더해줬다.
        list.add(num + 1);
    }

    static class Point {
        int y;
        int x;

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