[백준 2162] 선분 그룹

 

 기하학 알고리즘 문제. 로직도 또렷하게 떠오르고, 여러 개념을 버무릴 줄 알아야 하는 문제라 좋은 문제였다고 생각한다. 일단, 저번에도 한번 다룬적 있는 벡터의 외적을 활용한 CCW 알고리즘을 핵심으로 활용한다. 해당 알고리즘을 활용해서 두 선분이 만나는지 판별하는 것은 쉬운 일이지만, 이 문제에서는 만나는 선분끼리 그룹으로 분할한 정보를 알아내야 한다. 그러다보니 주의해야 할 케이스가 예제 1번과 같은 케이스이다.

 

 

 저런 케이스의 경우 1번 선분과 2번 선분만 입력되었을 때는 서로 다른 집합에 속하지만, 3번 선분이 더해지면서 같은 집합에 속하게 된다. 따라서 단순하게 앞서 등장했던 선분 집합에 대해, CCW를 통해 겹치는 선분이 존재하는 경우를 하나 찾아 그 집합에 해당 선분을 더해주는 방법은 적절하지 않다. 

 이 때 활용할 수 있는게 Union Find 알고리즘이다. 모든 선분들에 대해, 선형 탐색을 진행하면서, 앞서 등장한 선분들에 대해 모두 선분이 겹치는지 판별해 겹치는 선분마다 Union처리를 해둔다. 그렇다면 위의 케이스 같은 경우에도, 먼저 등장한 별개의 선분 집합들이 새로 등장한 선분에 의해 하나의 Union이 되도록 할 수 있다. 

 

 모든 선분에 대해 그룹 판별이 끝났다면, 모든 선분에 대해 선형 탐색을 하며 최대 크기 집합의 원소 수와 집합의 수를 출력할 수 있게 가공해준다. 나는 Map 자료구조를 활용했다(C++의 unordered_map이라 내부적으로는 해시 테이블이다). 이 때 각 root 값들에 바로 접근하지 말고 Union Find의 find() 함수를 통해 접근해서, 최종적인 루트노드를 갱신해서 가져온다. 

 만약에 Union 구조가 위와 같다면 1~5까지 처음 순회했을 때, root[3]값은 여전히 2일 것이기 때문에, Map에 그대로 넣게 되면 key가 1인 value와 2인 value가 모두 생기기 때문에 올바른 답을 구할 수 없다.

 Map을 완성한 이후엔 최대 값을 가지는 value를 찾으면 그게 가장 큰 선분 그룹의 원소 수가 되고, Map 내의 원소 수가 총 선분 그룹의 수가 된다.

 CCW 알고리즘에 대해서는 아래의 포스트에서 한 번 다루었기에 자세한 내용은 생략했다.
[백준 17387] 선분 교차 2 (tistory.com)

[백준 17387] 선분 교차 2

 

#include <iostream>
#include <vector>
#include <algorithm>
#include <unordered_map>

using namespace std;

typedef pair<int, int> point;
typedef pair<int, int> vec;

int root[3000]; 

int find(int x) {
    if(root[x]==x) {
        return x;
    } else {
        root[x] = find(root[x]);
        return root[x];
    }
}

void makeUnion(int x, int y) {
    x = find(x);
    y = find(y);

    if(x<=y) {
        root[y] = x;
    } else {
        root[x] = y;
    }
}

vec getVector(point start, point end) {
    return {end.first - start.first, end.second - start.second};
}

int getCCW(vec start, vec end) {
    int crossProduct = start.first*end.second - start.second*end.first;
    if(crossProduct > 0) {
        return 1;
    } else if(crossProduct == 0) {
        return 0;
    } else {
        return -1;
    };
}

bool isOnLine(point a1, point a2, point b) {
    int aMinX, aMaxX, aMinY, aMaxY;
    if(a1.first<a2.first) {
        aMinX = a1.first;
        aMaxX = a2.first;
    } else {
        aMinX = a2.first;
        aMaxX = a1.first;
    }

    if(a1.second<a2.second) {
        aMinY = a1.second;
        aMaxY = a2.second;
    } else {
        aMinY = a2.second;
        aMaxY = a1.second;
    }

    return aMinX<=b.first && aMaxX>=b.first && aMinY<=b.second && aMaxY>=b.second;
}

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

    int n;
    cin >> n;

    for(int i=0; i<n; i++) {
        root[i] = i;
    }

    vector<pair<point, point> > lineList;
    point p1, p2;

    for(int i=0; i<n; i++) {
        cin >> p1.first >> p1.second >> p2.first >> p2.second;

        for(int j=0; j<lineList.size(); j++) {
            pair<point, point> t = lineList[j];
            int pToT1, pToT2, tToP1, tToP2;

            pToT1 = getCCW(getVector(p1, p2), getVector(p2, t.first));    
            pToT2 = getCCW(getVector(p1, p2), getVector(p2, t.second));    
            tToP1 = getCCW(getVector(t.first, t.second), getVector(t.second, p1));    
            tToP2 = getCCW(getVector(t.first, t.second), getVector(t.second, p2));    

            if(pToT1==0 && isOnLine(p1, p2, t.first) ||
            pToT2==0 && isOnLine(p1, p2, t.second) ||
            tToP1==0 && isOnLine(t.first, t.second, p1) ||
            tToP2==0 && isOnLine(t.first, t.second, p2)) {
                makeUnion(i, j);
            } else if (pToT1*pToT2==-1 && tToP1*tToP2==-1) {
                makeUnion(i, j);
            }
        }

        lineList.push_back({p1, p2});
    }

    unordered_map<int, int> numTable;

    int rootNum, maxNum = 0;
    for(int i=0; i<n; i++) {
        rootNum = find(i);

        numTable[rootNum]++;
    }
    
    for(auto p: numTable) {
        maxNum = max(maxNum, p.second);
    }
    cout << numTable.size() << "\n" << maxNum;

}