백준 2162: 선분 그룹 C++

https://www.acmicpc.net/problem/2162

n개의 선분들이 각각 두 개의 좌표로 표현되어서 주어진다.

이 각각의 선분이 교차하는 경우에 같은 그룹으로 본다고 했을 때, 그룹의 수와 가장 멤버수가 많은 그룹에 속한 선분의 개수는?

[알고리즘]

1. 입력으로 들어오는 모든 선분들에 대해서 교차판별을 진행한다.

2. union-find를 활용해서, 교차한다면 같은 그룹으로 root를 묶어준다.

3. root인 선분의 개수를 파악한다. (root의 개수가 곧 그룹의 개수)

4. 그룹을 이루는 선분의 수가 가장 많은 그룹의 선분의 수를 파악한다.

[풀이]

교차 판별은 CCW를 활용한다. 1. 선분 A에 대해서 B의 각 점과 CCW를 돌리고, 2. 선분 B에 대해서 A의 각 점과 CCW를 돌린다.

1과 2의 결과가 모두 음수여야 기본적으로 교차할 수 있는 각도로 주어져있는 상태이다.

추가적으로 문제에서 관통하지 않고 딱 만나기만 해도 교차로 간주한다고 했으므로 위 조건에 0이 되는 경우까지 추가해야 한다.

이제 놓여있는 상태에 따라서 만날 수도 있고 아닐 수도 있다.

선분 A를 이루는 두 점의 x좌표가 선분 B를 이루는 두 점의 X좌표 모두보다 작다면 당연히 만날 수 없다. y좌표의 경우도 마찬가지.

그리고 선분 B에 대해서도 마찬가지이다. 이럴 경우에는 위의 CCW결과의 곱이 둘 다 음수로 나오더라도 만날 수 없는 경우이다.

이를 진행할 때, 만난다고 판단되는 경우 union작업을 해줘야 한다. union-find를 진행하기 위해, 부모 배열(r[])을 모두 자기 자신으로 초기화 해준다.

그리고 만난다고 판단되는 경우 union해준다.

이 작업을 마쳤다 하더라도, 모든 노드의 r[] 값이 최상위 부모로 갱신되었다는 보장이 없다. 따라서 getParent를 모든 지점에 대해 수행하여 r[] 값을 최상위 부모로 갱신해준다.

cnt[] 배열은 인덱스를 최상위 부모로 하는 선분의 수이다. cnt[1] = 3이라면, 1을 최상위 부모로하는 노드가 3개 있다는 것이다.

따라서 cnt[] 값이 0초과인 경우를 카운트 해주면, 그룹의 수를 셀 수 있다.

cnt[] 값이 최대인 곳이 최대 크기의 그룹일 것이다.

#include<iostream>
#include<algorithm>
#include<math.h>
using namespace std;
typedef long long ll;
struct LINE {
    int x1, y1, x2, y2;
 
};
LINE L[3001];
 
int r[3001]; // index의 root를 저장
int cnt[3001]; //index를 root로 하는 그룹 구성원 수
 
int getParent(int a) {
    if (r[a] == a) return a;
    else
        return r[a] = getParent(r[a]); //갱신하면서 찾으러 올라가야함
}
 
void join(int a, int b) {
    r[getParent(a)] = getParent(b);
}
 
ll ccw(int x1, int y1, int x2, int y2, int x3, int y3) { 
    ll ret = (x1*y2 + x2*y3 +x3*y1) - (y1*x2 + y2*x3 + y3*x1);
    if (ret < 0) return -1;
    else if (ret > 0) return 1;
    else return 0;
}
 
bool isCross(int x1, int y1, int x2, int y2, int x3, int y3, int x4, int y4) {
    //만나면 true, 아니면 false -> 선분 ccw 곱의 결과가 음수이지만 안 만나는 경우
    //예외 처리 필요 -> 0인 경우도 예외 처리에 포함시켜야함(평행이동 하면 관통안하고 만나기만하는 경우)
    if (ccw(x1, y1, x2, y2, x3, y3) * ccw(x1, y1, x2, y2, x4, y4) <= 0 &&
        ccw(x3, y3, x4, y4, x1, y1) * ccw(x3, y3, x4, y4, x2, y2) <= 0) {
        //여기까지 보면 각도 상으로는 만날 수 있는 조건을 갖춤
        if ((x1 > x3 && x1 > x4 && x2 > x3 && x2 > x4) ||
            (x3 > x1 && x3 > x2 && x4 > x1 && x4 > x2)) return false;
        else if ((y1 > y3 && y1 > y4 && y2 > y3 && y2 > y4) ||
            (y3 > y1 && y3 > y2 && y4 > y1 && y4 > y2)) return false;
        else
            return true;
    }
    return false; //애초에 양수면 교차X
}
int main() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) //유니온 파인드 할 때 편하라고 1-indexed
        cin >> L[i].x1 >> L[i].y1 >> L[i].x2 >> L[i].y2;
    
    for (int i = 1; i <= n; i++) r[i] = i; //root 자기 자신으로 초기화
 
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j < i; j++) {
            if (isCross(L[i].x1, L[i].y1, L[i].x2, L[i].y2, L[j].x1, L[j].y1, L[j].x2, L[j].y2))
                join(i, j);
        }
    }
    //여기까지 join해도, r[]이 최상위 부모노드를 가지지 않음. 따라서 추가 순회하면서 카운트
    for (int i = 1; i <= n; i++)
        cnt[getParent(i)]++;
    /* 부모 최신화와, 카운팅 분리
    for (int i = 1; i <= n; i++)
        int tmp = getParent(i);
    
    for (int i = 1; i <= n; i++)
        cnt[r[i]]++;
        */
    
    int groupCnt = 0, maxCnt = 0;
    for (int i = 1; i <= n; i++) {
        //cnt[]가 0이 아닌 곳이 그룹인 곳
        if (cnt[i] > 0) groupCnt++;
 
        if (cnt[i] > maxCnt) 
            maxCnt = cnt[i];    
    }
    cout << groupCnt << '\n' << maxCnt;
    return 0;
}

복습

//좌표값 정수
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
typedef long long ll;
struct POT {
    ll x, y;
    POT operator - (POT a) { return{x-a.x, y-a.y}; }
};
 
struct LINE {
    POT st, en;
}l[3001];
 
int n, r[3001], cnt[3001];
ll ccw(POT p1, POT p2) {
    ll ret = p1.x*p2.y - p1.y*p2.x;
    if (ret == 0) return 0;
    else if (ret > 0) return 1;
    else return -1;
}
ll ccw(POT p1, POT p2, POT p3) {
    return ccw(p2 - p1, p3 - p1);
}
int getPar(int a) {
    if (r[a] == a) return a;
    else
        return r[a] = getPar(r[a]);
}
void join(int a, int b) {
    a = getPar(a);
    b = getPar(b);
    if (a < b) 
        r[b] = a;
    
    else 
        r[a] = b;
    
}
bool isCross(LINE l1, LINE l2) {
    if (ccw(l1.st, l1.en, l2.st) * ccw(l1.st, l1.en, l2.en) <= 0 &&
        ccw(l2.st, l2.en, l1.st) * ccw(l2.st, l2.en, l1.en) <= 0) {
        if ((l1.st.x < l2.st.x && l1.st.x < l2.en.x && l1.en.x < l2.st.x&&l1.en.x < l2.en.x) ||
            (l2.st.x < l1.st.x && l2.st.x < l1.en.x && l2.en.x < l1.st.x&&l2.en.x < l1.en.x)) return false;
        if ((l1.st.y < l2.st.y && l1.st.y < l2.en.y && l1.en.y < l2.st.y&&l1.en.y < l2.en.y) ||
            (l2.st.y < l1.st.y && l2.st.y < l1.en.y && l2.en.y < l1.st.y&&l2.en.y < l1.en.y)) return false;
        return true;
    }
    return false; //안 만남
}
int main(void) {
    cin >> n;
    for(int i = 0 ; i < n ; i++)
        cin >> l[i].st.x >> l[i].st.y >> l[i].en.x >> l[i].en.y;
    
    for (int i = 0; i < n; i++) 
        r[i] = i; //자기 자신으로 최상위 부모 초기화
    
 
    //겹치면 union
    for (int i = 0; i < n; i++) 
        for (int j = i+1; j < n; j++) {
            if (isCross(l[i], l[j])) {
                join(i, j);
            }
        }
    
    for (int i = 0; i < n; i++)
        cnt[getPar(i)]++;
 
    int mx = -1, ct = 0;
    for (int i = 0; i < n; i++) {
        if (mx < cnt[i]) 
            mx = cnt[i];
        if (cnt[i] > 0) ct++;
    }
    printf("%d\n%d", ct, mx);
    return 0;
}