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

문제

풀이

1. 눈금을 칠한 곳을 못가게 visit에 저장
2. 눈금을 칠하지 않은 곳을 bfs()

ans - 영역의 수
arrayList - 영역의 크기들을 저장하는 배열

입력으로 받은 넓이만큼 visit[][]을 true로

맵을 전체 탐색하면서 visit[][]이 false면 ans++하고 bfs()시작
bfs()에서 새로운 눈금을 찾을 때 마다 max값을 +1하고 마지막에 return해서 영역의 크기를 반환

코드

전체코드

package baekjoon._2583;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {

    static int N, M, K, ans;
    static int[][] map;
    static Queue<int[]> queue;
    static boolean[][] visit;
    static int[][] dir = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

    public static void input() {
        FastReader fr = new FastReader();
        M = fr.nextInt();
        N = fr.nextInt();
        K = fr.nextInt();
        map = new int[M][N];
        visit = new boolean[M][N];
        for (int i = 0; i < K; i++) {
            int lx = fr.nextInt();
            int ly = fr.nextInt();
            int rx = fr.nextInt();
            int ry = fr.nextInt();
            for (int j = ly; j < ry; j++) {
                for (int k = lx; k < rx; k++) {
                    visit[j][k] = true;
                }
            }
        }
    }

    public static void main(String[] args) {
        input();
        ArrayList<Integer> arrayList = new ArrayList<>();
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < M; i++) {
            for (int j = 0; j < N; j++) {
                if(visit[i][j]) continue;
                ans++;
                arrayList.add(bfs(i, j));
            }
        }
        Collections.sort(arrayList);
        for (Integer integer : arrayList) {
            sb.append(integer);
            sb.append(" ");
        }
        System.out.println(ans);
        System.out.println(sb);
    }

    public static int bfs(int r, int c) {
        queue = new LinkedList<>();

        queue.add(new int[]{r, c, 1});
        visit[r][c] = true;
        int max = 1;

        while (!queue.isEmpty()) {
            int[] poll = queue.poll();
            int cr = poll[0];
            int cc = poll[1];
            for (int i = 0; i < 4; i++) {
                int nr = cr + dir[i][0];
                int nc = cc + dir[i][1];
                if(nr < 0 || nc < 0 || nr >= M || nc >= N) continue;
                if(visit[nr][nc]) continue;
                max++;
                visit[nr][nc] = true;
                queue.add(new int[]{nr, nc});
            }
        }
        return max;
    }

    static class FastReader {
        BufferedReader br;
        StringTokenizer st;

        public FastReader(){ br = new BufferedReader(new InputStreamReader(System.in));}

        String next(){
            while(st == null || !st.hasMoreTokens()){
                try{
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e){
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        int nextInt() { return Integer.parseInt(next()); }

        long nextLong() { return Long.parseLong(next()); }

        Double nextDouble() { return Double.parseDouble(next()); }

        String nextLine(){
            String str = "";
            try{
                str = br.readLine();
            } catch(IOException e){
                e.printStackTrace();
            }
            return str;
        }
    }
}

느낀점

그래프 탐색 문제 특히 BFS는 이제 쉽게 풀 수 있게 되었다.