P.2162 선분 그룹

코드

import java.io.*;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;

public class Main {

    static int n;
    static Line[] lines;
    static int[] parent;

    static public class Point implements Comparable{
        int x, y;

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

        @Override
        public int compareTo(Object o) {
            Point point = (Point) o;

            if (this.x == point.x) return this.y - point.y;
            else return this.x - point.x;
        }
    }

    static public class Line{
        Point p1, p2;

        public Line(Point p1, Point p2) {
            this.p1 = p1;
            this.p2 = p2;
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        n = Integer.parseInt(br.readLine());
        lines = new Line[n];
        for (int i = 0; i < n; i++) {
            int[] line = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
            Point p1 = new Point(line[0], line[1]);
            Point p2 = new Point(line[2], line[3]);
            lines[i] = new Line(p1, p2);
        }
        parent = new int[n];
        for (int i = 0; i < n; i++) parent[i] = i;

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (i == j) continue;

                if (!isSameParent(i, j)) {
                    if (checkCross(lines[i], lines[j])) {
                        union(i, j);
                    }
                }
            }
        }

        HashMap<Integer, Integer> map = new HashMap<>();
        for (int i : parent) {
            map.put(i, map.getOrDefault(i, 0) + 1);
        }

        int size = map.size();
        int cnt = 0;
        for (Integer value : map.values()) {
            cnt = Math.max(cnt, value);
        }

        bw.write(size + "\n" + cnt);
        bw.flush();
    }

    private static void union(int a, int b) {
        a = find(a);
        b = find(b);

        if (a < b) parent[b] = a;
        else parent[a] = b;
    }

    private static boolean isSameParent(int a, int b) {
        if (find(a) == find(b)) return true;
        else return false;
    }

    private static int find(int a) {
        if (parent[a] == a) return a;
        else return parent[a] = find(parent[a]);
    }

    private static boolean checkCross(Line l1, Line l2) {
        int ccw1 = ccw(l1.p1, l1.p2, l2.p1), ccw2 = ccw(l1.p1, l1.p2, l2.p2);
        int ccw3 = ccw(l2.p1, l2.p2, l1.p1), ccw4 = ccw(l2.p1, l2.p2, l1.p2);

        if (ccw1 * ccw2 <= 0 && ccw3 * ccw4 <= 0) {
            if (ccw1 * ccw2 == 0 && ccw3 * ccw4 == 0) {
                Point temp;

                if (l1.p1.compareTo(l1.p2) > 0) {
                    temp = l1.p1;
                    l1.p1 = l1.p2;
                    l1.p2 = temp;
                }
                if (l2.p1.compareTo(l2.p2) > 0) {
                    temp = l2.p1;
                    l2.p1 = l2.p2;
                    l2.p2 = temp;
                }

                if (l1.p1.compareTo(l2.p2) <= 0 && l1.p2.compareTo(l2.p1) >= 0) return true;
                else return false;
            }
            else return true;
        }
        return false;
    }

    private static int ccw(Point p1, Point p2, Point p3) {
        int res = (p1.x * p2.y + p2.x * p3.y + p3.x * p1.y) - (p2.x * p1.y + p3.x * p2.y + p1.x * p3.y);

        if (res > 0) return 1;
        else if (res == 0) return 0;
        else return -1;
    }
}

코드 설명

선분 교차 여부는 다음 알고리즘을 참고했다.

2023.09.11 - [코딩테스트/백준] - P.17387 선분 교차 2

P.17387 선분 교차 2

 

선분이 총 3000개이므로 이중 for문을 돌려도 시간 내에 해결 가능하다.

따라서 각각의 선분이 서로 교차하는지 여부는 이중 for문으로 해결했다.

 

이제 각각의 선분이 교차한다면 같은 그룹에 추가해야한다.

처음에는 각각의 그룹마다 인덱스를 두고 선분끼리의 인덱스(그룹 번호)가 같다면 같은 그룹 내에 있다고 생각하고 문제를 풀려고 했는데 이럴 경우, 같은 그룹 내에서도 인덱스가 여러 개가 생길 수 있다.

그래서 Union-Find함수를 이용했다.

루트가 같지 않으면 union해주는 건데 이 알고리즘은 크루스칼 알고리즘과 동일해서 다음 글의 크루스칼 알고리즘을 참고하면 된다.

2023.08.17 - [코딩테스트/백준] - P.1197 최소 스패닝 트리

P.1197 최소 스패닝 트리

 

유의해야할 점은 이중 for문을 다음처럼 돌리고, 루트의 동일 여부를 교차 여부보다 먼저 검사해야한다는 것이다.

for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
        if (i == j) continue;

        if (!isSameParent(i, j)) {
            if (checkCross(lines[i], lines[j])) {
                union(i, j);
            }
        }
    }
}

isSameParent에서 find를 해주며 루트를 업데이트 해주기 때문에 모든 선분에 대해서 isSameParent를 돌려 find를 해주어야 같은 그룹 내에서 인덱스가 달라지는 경우를 방지할 수 있다.