[백준/JAVA] 2162번: 선분 그룹

🔺 문제

2162번: 선분 그룹

 

 

🔺 코드

import java.util.*;
import java.io.*;
 
public class Main {
    static int[]   parent = new int[3001];   // 부모 노드 저장 배열
    static int[][] L = new int[3001][4];     // 선분 저장 배열
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        
        int N = Integer.parseInt(br.readLine());    // 선분 갯수
        for(int i = 1 ; i <= N ; i++) {
            parent[i] = -1;
        }
        
        // 신규 선분 저장
        for(int i = 1 ; i <= N ; i++) {
            st = new StringTokenizer(br.readLine()," ");
            L[i][0] = Integer.parseInt(st.nextToken());
            L[i][1] = Integer.parseInt(st.nextToken());
            L[i][2] = Integer.parseInt(st.nextToken());
            L[i][3] = Integer.parseInt(st.nextToken());
            
            // 이전에 저장된 선분들과 교차 여부 확인
            for(int j = 1 ; j < i ; j++) {
                if(isCross(L[i][0], L[i][1], L[i][2], L[i][3], L[j][0], L[j][1], L[j][2], L[j][3])) {
                    union(i, j);
                }
            }
        }
        
        int ans = 0;    // 선분 그룹 수
        int res = 0;    // 가장 큰 선분 그룹의 선분 수를 음수로 저장하는 변수
        for(int i = 1 ; i <= N ; i++) {
            if(parent[i] < 0) {                 // 음수면, 선분 그룹을 대표 부모 노드
                ans++;                          // 선분 그룹 수 증가
                res = Math.min(res, parent[i]); // 음수의 절댓값이 선분 그룹의 선분 개수
            }
        }
        System.out.println(ans);
        System.out.println(-res);
    }
    
    // 유니온파인드
    static int find(int i) {
        if(parent[i] < 0) return i;
        return parent[i] = find(parent[i]);
    }    
    static void union(int a, int b) {
        int p = find(a);
        int q = find(b);
        
        if(p == q)  return;     // 이미 연결됨
        parent[p] += parent[q]; // p의 부모 노드에 q가 속한 선분 그룹의 선분 개수 더하기
        parent[q] = p;          // p를 q의 부모 노드로 저장
    }
    
    // CCW
    private static int CCW(long x1, long y1, long x2, long y2, long x3, long y3) {
        long tmp = (x1*y2 + x2*y3 + x3 * y1) - (x2*y1 + x3*y2 + x1*y3);
        
        if(tmp > 0)      return 1;  // 반시계
        else if(tmp < 0) return -1; // 시계
        return 0;                   // 일직선
    }
    
    // 선분 겹치는지 판단
    private static boolean isOverlap(long x1, long y1, long x2, long y2, long x3, long y3, long x4, long y4) {
        if(Math.min(x1, x2) <= Math.max(x3, x4) && Math.min(x3, x4) <= Math.max(x1, x2)
        && Math.min(y1, y2) <= Math.max(y3, y4) && Math.min(y3, y4) <= Math.max(y1, y2))
            return true;
        return false;
    }
    
    // 교차 여부 판단
    private static boolean isCross(long x1, long y1, long x2, long y2, long x3, long y3, long x4, long y4) {
        int abc = CCW(x1, y1, x2, y2, x3, y3);
        int abd = CCW(x1, y1, x2, y2, x4, y4);
        int cda = CCW(x3, y3, x4, y4, x1, y1);
        int cdb = CCW(x3, y3, x4, y4, x2, y2);
        
        // 선분이 일직선일 때
        if(abc * abd == 0 && cda * cdb == 0) {
            return isOverlap(x1, y1, x2, y2, x3, y3, x4, y4);
        }
        // 선분이 교차하는 경우
        else if(abc * abd <= 0 && cda * cdb <= 0) {
            return true;
        }
        return false;
    }
}

✅ 해결 아이디어
✔ 분리 집합 & 선분 교차 판정

---

🔺 다른 풀이들

- 멋진 해설... 

[BOJ] 백준 2162번 : 선분 그룹 (JAVA)

[백준] 2162번 선분 그룹 / Java, Python

---

💬 느낀 점

유니온 파인드 오랜만입니다ㅎㅎ

 

 

1회독	2회독	3회독	4회독	5회독
V

---

(참고)

✔ Do it 알고리즘 코딩테스트 자바편