[백준, 자바, 2583번] 영역 구하기

풀이

• 해당 문제는 크게 뭐 문제가 있었던 건 없지만
• 입력 값에서 이해를 다르게 해서 뭔가 싶었다.
• 만약 입력값이 0 2 4 4 라면
  • 0,2 부터 4,4까지라는 건줄 알았는데
  • 2,0 부터 4,4전인 3,3까지라는 말임.
• 그래서 이후 쉽게 해결

 

import java.io.*;
import java.util.*;
import java.util.stream.Collectors;
public class _2583 {
    static List<Integer> result = new ArrayList<>();
    static int M;
    static int N;
    static int K;
    static boolean[][] mtx;
    static Deque<List<Integer>> dq = new ArrayDeque<>();

    static int[] di = {-1,0,1,0};
    static int[] dj = {0,1,0,-1};
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int[] MNK = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        M = MNK[0];
        N = MNK[1];
        K = MNK[2];

        mtx = new boolean[M][N];


        for (int x=0; x<K; x++) {
            int[] li = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
            for (int i=li[1]; i<li[3]; i++) {
                for (int j=li[0]; j<li[2]; j++) {
                    if (!mtx[i][j]) mtx[i][j] = true;
                }
            }
        }
        for (int i=0; i<M; i++) {
            for (int j=0; j<N; j++) {
                if (!mtx[i][j]) {
                    dq.add(new ArrayList<>(Arrays.asList(i,j)));
                    mtx[i][j] = true;
                    result.add(find());
                }
            }
        }
        Collections.sort(result);
        System.out.println(result.size());
        System.out.println(result.stream().map(String::valueOf).collect(Collectors.joining(" ")));
    }

    public static int find() {
        int cnt = 1;
        while (!dq.isEmpty()) {
            List<Integer> li = dq.pollFirst();
            for (int t=0; t<4; t++) {
                int ni = di[t]+li.get(0);
                int nj = dj[t]+li.get(1);
                if ((0<=ni&&ni<M) && (0<=nj&&nj<N) && !mtx[ni][nj]) {
                    mtx[ni][nj] = true;
                    dq.add(new ArrayList<>(Arrays.asList(ni,nj)));
                    cnt++;
                }
            }
        }
        return cnt;
    }
}