[자바] 백준 2162 - 선분 그룹 (java)

 문제 : boj2162

---

 

필요 알고리즘 개념

• 분리 집합
  
  • 그룹의 개수 및 그룹의 크기를 구하기 위해 분리 집합 알고리즘을 알고 있으면 좋다(안써서 푼 사람들도 있긴하다).

• 선분 교차 판정 (기하학, CCW)
  
  • 선분 교차 판정 알고리즘으로 풀 수 있다.

※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다.

 

---

 

풀이

  내 경우 union-find를 쓸 때, 코드상의 parents 배열 기준으로 그룹의 메인 번호는 음수, 나머지는 양수로 메인 번호를 나타내도록 했다. 따라서 이후 그룹의 수는 parents 배열에서 음수인 노드의 수가 된다. 그리고 해당 그룹에 들어있는 노드들의 수는 메인 노드에 음수로 나타냈다. 즉, -5라면 해당 그룹에 5개의 노드가 있는 것이다. 따라서 가장 크기가 큰 그룹에 속한 선분의 개수도 출력할 수 있게 된다.

 

  그럼 이제 해야될건 선분 교차 판정을 NxN개의 모든 선분에 대해 수행해서 교차한다면 그룹을 합치는 과정이다. 선분 교차 판정의 경우 CCW를 이용한 선분 교차 여부 판정을 보고 구현해주면 된다.

for (int i = 0; i < n; i++) {	//N개에 대해
    for (int j = i+1; j < n; j++) {	//N개를 전부 보면서. 다만 A B를 봤다면 B A는 볼 필요 없으므로 j=i+1부터 보면 된다.
        if (lines[i].isIntersection(lines[j]))	// 선분이 교차한다면
            uf.union(i, j);	// 그룹을 합친다
    }
}

 

  주의점은 자바8로 제출 시 메모리 초과가 날 가능성이 있으니 자바9 이상으로 제출하자.

맞왜틀을 외치며 메모리를 최적화했는데, 자바 11, 15로는 그냥 쉽게 통과됬다 ㅠ 자바8은 Parallel이 기본 GC이고, 자바9 이후로는 G1 GC가 기본 GC인데 이 문제의 경우 후자가 더 성능이 좋게 나타나서 그럴 것 같다.

 

---

 

코드 : github

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

class Point implements Comparable<Point> {
    int x, y;
    public Point(int x, int y) {
        this.x = x;
        this.y = y;
    }
    @Override
    public int compareTo(Point o) {
        if (this.x == o.x)
            return this.y-o.y;
        return this.x-o.x;
    }
}

class Line {
    Point a, b;
    public Line(Point p1, Point p2) {
        a = p1.compareTo(p2)<=0?p1:p2;
        b = p1.compareTo(p2)<=0?p2:p1;
    }
    public Line(int x1, int y1, int x2, int y2) {
        this(new Point(x1, y1), new Point(x2, y2));
    }
    public boolean isIntersection(Line ano) {
        int res1 = Ccw.getCcw(this.a, this.b, ano.a) * Ccw.getCcw(this.a, this.b, ano.b);
        int res2 = Ccw.getCcw(ano.a, ano.b, this.a) * Ccw.getCcw(ano.a, ano.b, this.b);
        if (res1==0&&res2==0) {
            return this.a.compareTo(ano.b)<=0 && ano.a.compareTo(this.b)<=0;
        }
        return res1<=0 && res2<=0;
    }
}

class Ccw {
    public static int getCcw(Point a, Point b, Point c) {
        Point[] arr = {a,b,c,a};
        int sum = 0;
        for (int i = 0; i < 3; i++) {
            sum += arr[i].x*arr[i+1].y-arr[i+1].x*arr[i].y;
        }
        return sum>0?1:sum<0?-1:0;
    }
}

class UnionFind {
    int[] parents;

    public UnionFind(int num) {
        parents = new int[num];
        Arrays.fill(parents, -1);
    }

    public int find(int a) {
        if (parents[a] < 0) return a;
        return parents[a] = find(parents[a]);
    }

    public void union(int a, int b) {
        a = find(a);
        b = find(b);
        if (a == b) return;
        int h = parents[a]<parents[b]?a:b;
        int l = parents[a]<parents[b]?b:a;
        parents[h] += parents[l];
        parents[l] = h;
    }
}

public class Main {
    UnionFind uf;
    private int ni(StringTokenizer st) { return Integer.parseInt(st.nextToken()); }
    private void solution() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in), 1<<16);
        int n = Integer.parseInt(br.readLine());
        uf = new UnionFind(n);
        Line[] lines = new Line[n];
        StringTokenizer st;
        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            lines[i] = new Line(ni(st), ni(st), ni(st), ni(st));
        }
        
        for (int i = 0; i < n; i++) {
            for (int j = i+1; j < n; j++) {
                if (lines[i].isIntersection(lines[j]))
                    uf.union(i, j);
            }
        }

        int cnt = 0;
        int min = 0;
        for (int i = 0; i < n; i++) {
            if (uf.parents[i] < 0) {
                cnt++;
                if (uf.parents[i] < min)
                    min = uf.parents[i];
            }
        }
        System.out.printf("%d\n%d\n", cnt, -min);
    }

    public static void main(String[] args) throws Exception {
        new Main().solution();
    }
}