백준 2583 영역 구하기

정말 여러번 틀렸는데, 아쉬운점은 정렬을 확인 해볼 생각을 하지 않았다는 거였다. 정렬을 이상한 컬렉션을 이용해서 지금까지 정렬이 제대로 되고 있지 않던 거였는데, 다행히 해결했다.

 

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashSet;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Scanner;
import java.util.StringTokenizer;

public class Main {

    public static void main(String[] args) {
        int m,n,k;
        int table[][] = new int[102][102];                  //0으로 초기화 되어있나?

        Scanner scanner = new Scanner(System.in);
        StringTokenizer stringTokenizer = new StringTokenizer(scanner.nextLine());
        Queue<Pair> q = new LinkedList();
        List <Integer> dir_x = List.of(1, 0, -1, 0);
        List <Integer> dir_y = List.of(0, 1, 0, -1);

        m = Integer.parseInt(stringTokenizer.nextToken());
        n = Integer.parseInt(stringTokenizer.nextToken());
        k = Integer.parseInt(stringTokenizer.nextToken());

        for (int i = 0; i < k; i++) {
            stringTokenizer = new StringTokenizer(scanner.nextLine());
            int x1 = Integer.parseInt(stringTokenizer.nextToken());
            int y1 = Integer.parseInt(stringTokenizer.nextToken());
            int x2 = Integer.parseInt(stringTokenizer.nextToken());
            int y2 = Integer.parseInt(stringTokenizer.nextToken());

            for (int garo = y1; garo < y2; garo++) {
                for (int sero = x1; sero < x2; sero++) {
                    table[garo][sero] = 1;
                }
            }
        }
        int cnt = 0;
        ArrayList<Integer> width = new ArrayList<>();

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (table[i][j] == 0) {
                    q.add(new Pair(i,j));
                    table[i][j] = 1;
                    int size_tmp = 0;
                    while (!q.isEmpty()) {
                        Pair cur = q.peek();
                        q.remove();
                        size_tmp++;
                        for (int dir = 0; dir < 4; dir++) {
                            int nx = cur.x + dir_x.get(dir);
                            int ny = cur.y + dir_y.get(dir);
                            if (nx < 0 || nx >= m || ny < 0 || ny >= n) continue;
                            if (table[nx][ny] == 1) continue;
                            table[nx][ny] = 1;
                            q.add(new Pair(nx, ny));
                        }
                    }
                    width.add(size_tmp);
                }
            }
        }
        Iterator iter = width.iterator();
        System.out.println(width.size());
        Collections.sort(width);
        int cur = 0;

        for (int i = 0; i < width.size(); i++) {
            System.out.print(width.get(i) + " ");
        }

        System.out.println();

    }

    public static class Pair {
        int x;
        int y;

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

 

width.stream().sorted();

 

이거로 정렬을 했었는데, 이걸로 하면 문제가 생기기 때문에 처음 넓이들을 저장하는 배열을 그냥 arrayList 를 이용하였고, 

 

Collections.sort(width);

collections.sort() 를 이용해 정렬했다.

 

Pair class 를 만들어 사용하였다.