🏆 [Baekjoon / Java] 2162. 선분 그룹

문제 설명

💡 Info

• 난이도 : 플래티넘 V
• 시간 제한 : 2초
• 메모리 제한 : 128MB
• 백준 링크: https://www.acmicpc.net/problem/2162
  풀이 링크(GitHub): hayannn/CodingTest_Java/백준/Platinum/2162. 선분 그룹

내용

N개의 선분들이 2차원 평면상에 주어져 있다. 선분은 양 끝점의 x, y 좌표로 표현이 된다.

두 선분이 서로 만나는 경우에, 두 선분은 같은 그룹에 속한다고 정의하며, 그룹의 크기는 그 그룹에 속한 선분의 개수로 정의한다. 두 선분이 만난다는 것은 선분의 끝점을 스치듯이 만나는 경우도 포함하는 것으로 한다.

N개의 선분들이 주어졌을 때, 이 선분들은 총 몇 개의 그룹으로 되어 있을까? 또, 가장 크기가 큰 그룹에 속한 선분의 개수는 몇 개일까? 이 두 가지를 구하는 프로그램을 작성해 보자.

📥입력 조건

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

# 1
3
1 1 2 3
2 1 0 0
1 0 1 1

# 2
3
-1 -1 1 1
-2 -2 2 2
0 1 -1 0

📤출력 조건

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

# 1
1
3

# 2
2
2

문제 이해

• 선분의 교차 여부 확인 -> 이것으로 그룹화 및 그룹별로 최대 크기를 계산해서 출력하는 문제

알고리즘 및 최종 풀이

실제 풀이 시간 : 1시간 20분(첫 풀이 시간 포함)

• 입력
  • 선분들의 좌표를 입력
• 계산
  • Union-Find 수행
    • 선분들의 교차 여부 확인
      • 교차하는 선분은 Union 연산으로 그룹 합치기
  • 교차 여부 확인
    • ccw
      • 세 점이 이루는 방향 계산
    • meet
      • 두 선분의 교차 여부 확인 -> 교차하면 Union 연산 수행
  • 그룹 계산
    • 그룹 내 속하는 선분 개수 구하기(가장 큰 값)
    • 그 그룹 저장
• 출력
  • 그룹 개수, 가장 큰 그룹 크기를 출력

import java.util.*;

public class Main {

    static int[] parent;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        Line[] lines = new Line[n];
        parent = new int[n];

        for (int i = 0; i < n; i++) {
            lines[i] = new Line(sc.nextInt(), sc.nextInt(), sc.nextInt(), sc.nextInt());
            parent[i] = i;
        }

        for (int i = 0; i < n - 1; i++) {
            for (int j = i + 1; j < n; j++) {
                if (meet(lines[i], lines[j])) {
                    union(i, j);
                }
            }
        }

        Map<Integer, Integer> groupCount = new HashMap<>();
        int maxSize = 1;

        for (int i = 0; i < n; i++) {
            int groupParent = getParent(i);
            groupCount.put(groupParent, groupCount.getOrDefault(groupParent, 0) + 1);
            maxSize = Math.max(maxSize, groupCount.get(groupParent));
        }

        System.out.println(groupCount.size());
        System.out.println(maxSize);
    }

    static int getParent(int idx) {
        if (parent[idx] != idx) {
            parent[idx] = getParent(parent[idx]);
        }
        return parent[idx];
    }

    static boolean meet(Line l1, Line l2) {
        int res1 = ccw(l1, l2.x1, l2.y1) * ccw(l1, l2.x2, l2.y2);
        int res2 = ccw(l2, l1.x1, l1.y1) * ccw(l2, l1.x2, l1.y2);

        if (res1 == 0 && res2 == 0) {
            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);
        } else {
            return res1 <= 0 && res2 <= 0;
        }
    }

    static int ccw(Line l1, int x3, int y3) {
        int x1 = l1.x1, y1 = l1.y1, x2 = l1.x2, y2 = l1.y2;
        long result = (long) (x2 - x1) * (y3 - y1) - (long) (y2 - y1) * (x3 - x1);
        if (result == 0) return 0;
        return result > 0 ? 1 : -1;
    }

    static void union(int i, int j) {
        int rootI = getParent(i);
        int rootJ = getParent(j);
        if (rootI != rootJ) {
            parent[rootI] = rootJ;
        }
    }

    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;
        }
    }
}