BOJ 2162 - 선분 그룹 링크
(2023.04.21 기준 P5)

문제

양 끝점의 x, y 좌표로 구현이 되는 선분이 N개가 주어진다.
두 선분이 서로 만나는 경우에 같은 그룹에 속한다고 정의한다면, 그룹이 총 몇 개인지와 크기가 가장 큰 그룹에 속한 선분의 개수 출력

알고리즘

문제에 그대로 나와 있다. 선분이 만나는 것은 선분 교차 판정. 그룹으로 묶는 것은 분리 집합.

풀이

우리가 구해야 하는 것은 두 가지. 그룹의 개수, 가장 큰 그룹의 크기.
크기는 다음과 같이 구하자.

함수 union(u, v):
	parent[u] = v
    size[v] += size[u]

설명을 간략히 하자면, 위 코드는 u와 v를 합치는데, u의 부모가 v를 가르키게 되므로, u를 v에 속하게 하는 것이다. 그러면 v의 크기는 u의 크기만큼 늘어날 것이다.
size 배열을 1로 초기화(각 집합은 선분 하나씩 있으므로), 그리고 위와 같이 해주면 된다.

이제 그룹으로 묶는 기준은 선분 교차 판정으로 잡으면 된다.
교차 판정은 ccw로 하면 된다.
교차하는 경우엔 각 ccw의 방향이 다른 것을 볼 수 있다.
하지만 두 선분이 일직선 상에 있을 수 있다. 그럴 땐
이렇게 x, y좌표의 대소 관계로 파악하면 된다.

코드

• C++

#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

vector<int> pa(3000);
vector<int> sz(3000);

int find(int u){
    if (pa[u] != u) pa[u] = find(pa[u]);
    return pa[u];
}

void merge(int u, int v){
    u = find(u);
    v = find(v);

    // 부모가 같다면 합치지 않는다.
    if (u < v) pa[v] = u, sz[u] += sz[v];
    else if (u > v) pa[u] = v, sz[v] += sz[u];
}

ll ccw(pii a, pii b, pii c){
    return (ll)(a.x * b.y + b.x * c.y + c.x * a.y) - (a.y * b.x + b.y * c.x + c.y * a.x);
}

bool is_intersect(pii a, pii b, pii c, pii d){ // 선분 교차 판정
    ll ab = ccw(a, b, c) * ccw(a, b, d);
    ll cd = ccw(c, d, a) * ccw(c, d, b);
    if (!ab && !cd){ // 두 선분의 네 점이 일직선 상에 있는 경우
        if (a > b) swap(a, b);
        if (c > d) swap(c, d);
        return c <= b && a <= d;
    }
    return ab <= 0 && cd <= 0;
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int N;
    cin >> N;

    vector<pii> pos[N];
    for (int i = 0, x1, y1, x2, y2; i < N; i++){
        cin >> x1 >> y1 >> x2 >> y2;
        pos[i].push_back({x1, y1}); // 선분의 시작점
        pos[i].push_back({x2, y2}); // 선분의 끝점
    }

    iota(pa.begin(), pa.begin() + N, 0); // 부모
    fill(sz.begin(), sz.begin() + N, 1); // 크기
    for (int i = 0; i < N - 1; i++) for (int j = i + 1; j < N; j++)
        if (is_intersect(pos[i][0], pos[i][1], pos[j][0], pos[j][1])) merge(i, j);

    // 각 자식들이 가리키고 있던 부모가 다른 부모를 가르키고 있을 수 있다.
    // 이 경우에 가리키고 있던 부모를 다시 진짜 부모로 바꿔줘야 한다.
    set<int> parent;
    for (int i = 0; i < N; i++) pa[i] = find(pa[i]), parent.insert(pa[i]);

    cout << parent.size() << '\n' << *max_element(sz.begin(), sz.begin() + N);
}

• Python

import sys; input = sys.stdin.readline

def find(u):
    if parent[u] != u:
        parent[u] = find(parent[u])
    return parent[u]

def union(u, v):
    u = find(u)
    v = find(v)

    # 부모가 같다면 합치지 않는다.
    if u < v:
        parent[v] = u
        size[u] += size[v]
    elif v < u:
        parent[u] = v
        size[v] += size[u]

def ccw(a, b, c):
    return (a[0] * b[1] + b[0] * c[1] + c[0] * a[1]) - (a[1] * b[0] + b[1] * c[0] + c[1] * a[0])

def is_intersect(a, b, c, d): # 선분 교차 판정
    ab = ccw(a, b, c) * ccw(a, b, d)
    cd = ccw(c, d, a) * ccw(c, d, b)
    if not ab and not cd: # 두 선분의 네 점이 일직선 상에 있는 경우
        if a > b:
            a, b = b, a
        if c > d:
            c, d = d, c
        return c <= b and a <= d
    return ab <= 0 and cd <= 0

N = int(input())

pos = [[] for _ in range(N)]
for i in range(N):
    x1, y1, x2, y2 = map(int, input().split())
    pos[i].append((x1, y1)) # 선분의 시작점
    pos[i].append((x2, y2)) # 선분의 끝점

parent = [i for i in range(N)] # 부모
size = [1] * N # 크기
for i in range(N - 1):
    for j in range(i + 1, N):
        if is_intersect(pos[i][0], pos[i][1], pos[j][0], pos[j][1]):
            union(i, j)

# 각 자식들이 가리키고 있던 부모가 다른 부모를 가르키고 있을 수 있다.
# 이 경우에 가리키고 있던 부모를 다시 진짜 부모로 바꿔줘야 한다.
for i in range(N):
    parent[i] = find(parent[i])

print(len(set(parent)))
print(max(size))