[ 백준 ] 2162번 - 선분 그룹 (C++)

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

2162번: 선분 그룹

 

 

[ 문제풀이 ]

 

https://rudalsd.tistory.com/5

[ 백준 ] 17387번 - 선분 교차 2 (C++)

 

위 문제를 풀어보고 오는 것을 추천드립니다!

 

이 문제는 선분 교차 2 문제에서 Union - Find를 추가한 문제입니다. 직선의 개수가 3000개밖에 되지 않으므로 2중 for문을 돌려도 큰 문제가 없으므로 2중 for문으로 문제를 풀었습니다. 선분이 교차한다면 Union을 해주고 마지막에 모든 선분을 돌면서 Find를 통해 map에 부모 노드를 저장해줍니다.

 

그리고 map.size()와 map[ i ]의 값 중 제일 큰 값을 출력해주면 됩니다.

 

[ 소스 코드 ]

#include <iostream>
#include <algorithm>
#include<unordered_map>
 
using namespace std;
 
struct pos {
    int x;
    int y;
};
 
pos arr[6000];
int vect[3001];
unordered_map<int, int> m;
 
int N;
 
int Find(int n)
{
    if (vect[n] == n) return n;
    return vect[n] = Find(vect[n]);
}
 
void Union(int a, int b)
{
    int pa = Find(a);
    int pb = Find(b);
 
    if (pa != pb) {
        vect[pb] = pa;
    }
}
 
bool cmp(pos left, pos right)
{
    if (left.x == right.x) return left.y <= right.y;
    return left.x <= right.x;
}
 
int closs(pos p1, pos p2, pos p3) {         //외적을 통해 방향을 리턴
    int cross_product = (p2.x - p1.x) * (p3.y - p1.y) - (p3.x - p1.x) * (p2.y - p1.y);
 
    if (cross_product > 0) {
        return 1;
    }
    else if (cross_product < 0) {
        return -1;
    }
    else {
        return 0;
    }
}
 
int main()
{
    cin >> N;
 
    for (int i = 0; i < N * 2; i++) {
        cin >> arr[i].x >> arr[i].y;
    }
 
    for (int i = 0; i < N ; i++) {
        sort(arr + i * 2, arr + (i + 1) * 2, cmp);
    }
 
    for (int i = 0; i < N; i++) {
        vect[i] = i;
    }
 
    for (int i = 0; i < N - 1; i++) {
        for (int j = i + 1; j < N; j++) {
            int l1 = closs(arr[i * 2], arr[i * 2 + 1], arr[j * 2]) * closs(arr[i * 2], arr[i * 2 + 1], arr[j * 2 + 1]);
            int l2 = closs(arr[j * 2], arr[j * 2 + 1], arr[i * 2]) * closs(arr[j * 2], arr[j * 2 + 1], arr[i * 2 + 1]);
            if (l1 == 0 && l2 == 0) {            //두 선이 일직선상에 있을 때
                if (cmp(arr[j*2], arr[i*2+1]) && cmp(arr[i*2], arr[j*2+1])) {
                    if (Find(i) != Find(j)) {
                        Union(i, j);
                    }
                }
            }
            else if (l1 <= 0 && l2 <= 0) {
                if (Find(i) != Find(j)) {
                    Union(i, j);
                }
            }
        }
    }
 
    for (int i = 0; i < N; i++) {
        m[Find(i)]++;        //집합에 속해있다면 선분을 map에 추가
    }
 
    int ans = 0;
 
    for (auto it = m.begin(); it != m.end(); it++) {
        if (ans < it->second) {    //집합 중 가장 큰 집합을 ans에 대입
            ans = it->second;
        }
    }
 
    cout << m.size() << endl << ans;
}