백준 선분 그룹

문제

내가 생각했을때 문제에서 원하는부분

첫째 줄에 N(1 ≤ N ≤ 3,000)이 주어진다.
둘째 줄부터 N+1번째 줄에는 양 끝점의 좌표가 x1, y1, x2, y2의 순서로 주어진다.
각 좌표의 절댓값은 5,000을 넘지 않으며, 입력되는 좌표 사이에는 빈칸이 하나 있다.

첫째 줄에 그룹의 수를, 둘째 줄에 가장 크기가 큰 그룹에 속한 선분의 개수를 출력한다.

내가 이 문제를 보고 생각해본 부분

Line 클래스는 한 선분의 두 끝점 좌표를 저장한다.
Union-Find (Disjoint Set) 자료구조를 구현해, 선분 그룹을 합치는 데 사용한다.
입력받은 선분 배열에 대해 모든 쌍에 대해 교차 여부를 검사한다.
isIntersect 함수는 두 선분이 서로 만나는지 판단한다.
CCW (Counter Clock Wise) 알고리즘을 사용해 교차 여부를 판정한다.
두 선분이 한 직선 위에 있으면 isOverlap 함수로 범위가 겹치는지 확인한다.
교차하면 Union-Find를 통해 두 선분을 같은 그룹으로 병합한다.
모든 선분 그룹이 완성되면 전체 그룹 수와 가장 큰 그룹의 크기를 계산해 출력한다.

코드로 구현

package baekjoon.baekjoon_33;

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

// 백준 2162번 문제
public class Main1348 {
    static int[] parent;
    static int[] size;

    static class Line {
        int x1, y1, x2, y2;
        public Line(int x1, int y1, int x2, int y2) {
            this.x1 = x1; this.y1 = y1; this.x2 = x2; this.y2 = y2;
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());

        Line[] lines = new Line[N];
        for (int i = 0; i < N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int x1 = Integer.parseInt(st.nextToken());
            int y1 = Integer.parseInt(st.nextToken());
            int x2 = Integer.parseInt(st.nextToken());
            int y2 = Integer.parseInt(st.nextToken());
            lines[i] = new Line(x1, y1, x2, y2);
        }

        parent = new int[N];
        size = new int[N];
        for (int i = 0; i < N; i++) {
            parent[i] = i;
            size[i] = 1;
        }

        // 모든 선분 쌍에 대해 교차 판정 후 Union
        for (int i = 0; i < N; i++) {
            for (int j = i + 1; j < N; j++) {
                if (isIntersect(lines[i], lines[j])) {
                    union(i, j);
                }
            }
        }

        // 그룹 개수와 가장 큰 그룹 크기 찾기
        int groupCount = 0;
        int maxSize = 0;
        boolean[] counted = new boolean[N];
        for (int i = 0; i < N; i++) {
            int p = find(i);
            if (!counted[p]) {
                counted[p] = true;
                groupCount++;
                if (size[p] > maxSize) {
                    maxSize = size[p];
                }
            }
        }

        System.out.println(groupCount);
        System.out.println(maxSize);
        br.close();
    }

    // Union-Find find 함수
    static int find(int x) {
        if (parent[x] == x) return x;
        return parent[x] = find(parent[x]);
    }

    // Union-Find union 함수
    static void union(int a, int b) {
        a = find(a);
        b = find(b);
        if (a != b) {
            if (size[a] < size[b]) {
                int temp = a;
                a = b;
                b = temp;
            }
            parent[b] = a;
            size[a] += size[b];
        }
    }

    // 벡터 외적 (Cross product)
    static long ccw(int x1, int y1, int x2, int y2, int x3, int y3) {
        return (long)(x2 - x1) * (y3 - y1) - (long)(y2 - y1) * (x3 - x1);
    }

    // 두 선분이 교차(또는 끝점 스치는 포함)하는지 판정
    static boolean isIntersect(Line l1, Line l2) {
        long ccw1 = ccw(l1.x1, l1.y1, l1.x2, l1.y2, l2.x1, l2.y1) * ccw(l1.x1, l1.y1, l1.x2, l1.y2, l2.x2, l2.y2);
        long ccw2 = ccw(l2.x1, l2.y1, l2.x2, l2.y2, l1.x1, l1.y1) * ccw(l2.x1, l2.y1, l2.x2, l2.y2, l1.x2, l1.y2);

        if (ccw1 > 0 || ccw2 > 0) {
            return false; // 두 선분이 서로 다른 방향에 있음 (교차 안함)
        }

        if (ccw1 == 0 && ccw2 == 0) {
            // 일직선상에 있으면 한 선분의 좌표가 다른 선분의 범위 내에 있어야 함
            return isOverlap(l1, l2);
        }
        return true;
    }

    // 두 선분이 일직선상이고 겹치는지 확인
    static boolean isOverlap(Line l1, Line l2) {
        return Math.min(l1.x1, l1.x2) <= Math.max(l2.x1, l2.x2) &&
                Math.min(l2.x1, l2.x2) <= Math.max(l1.x1, l1.x2) &&
                Math.min(l1.y1, l1.y2) <= Math.max(l2.y1, l2.y2) &&
                Math.min(l2.y1, l2.y2) <= Math.max(l1.y1, l1.y2);
    }
}

마무리

코드와 설명이 부족할수 있습니다. 코드를 보시고 문제가 있거나 코드 개선이 필요한 부분이 있다면 댓글로 말해주시면 감사한 마음으로 참고해 코드를 수정 하겠습니다.