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

 

 

<코드>

#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;

#define X first
#define Y second
typedef pair<int, int> pii;

int N, group_num, seg_num;
bool visit[3001];
int parent[3001];
vector<int> graph[3001];
vector<pii> v[3001];
queue<int> q;

int CCW(pii A, pii B, pii C)
{
	int tmp = A.X * B.Y + B.X * C.Y + C.X * A.Y;
	tmp -= B.X * A.Y + C.X * B.Y + A.X * C.Y;

	if (tmp > 0) return 1; // 반시계
	else if (tmp == 0) return 0; // 일직선
	else if (tmp < 0) return -1; // 시계방향
}

bool check(pii A, pii B, pii C, pii D) // 두 선분 교차 여부
{
	int ans1 = CCW(A, B, C) * CCW(A, B, D);
	int ans2 = CCW(C, D, A) * CCW(C, D, B);

	if (ans1 == 0 && ans2 == 0) // 평행 혹은 양 끝점이 접촉해 있을 때
	{
		if (A > B) swap(A, B);
		if (C > D) swap(C, D);
		
		if (A <= D && B >= C) return true;
		else return false;
	}
	else 
	{
		// 교차 혹은 한 점이 선분 위에 있을 때(끝점 x)
		if (ans1 <= 0 && ans2 <= 0) return true;
		else return false;
	}
}

int find_parent(int u) // 부모 노드 찾기
{
	if (u == parent[u]) return u;
	else return parent[u] = find_parent(parent[u]);
}

bool union_segment(int u, int v) // 노드 연결
{
	u = find_parent(u);
	v = find_parent(v);

	// 부모 노드가 같다면 싸이클이 생기므로 건너뜀
	if (u == v) return false;
	else
	{
		// 부모 노드 지정
		parent[u] = v;

		// 노드 연결 표시
		graph[u].push_back(v);
		graph[v].push_back(u);

		return true;
	}
}

void BFS(int x) // 연결된 노드 수 판별
{
	int num = 1; // 현재 그룹에 속한 선분 수
	q.push(x); // 시작노드

	while (!q.empty())
	{
		int now = q.front();
		q.pop();

		visit[now] = true;
		for (int i = 0; i < graph[now].size(); i++)
		{
			int next = graph[now][i];

			if (!visit[next]) // 방문하지 않았다면
			{
				num++;
				q.push(next);
			}
		}
	}

	seg_num = max(seg_num, num);
}

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

	cin >> N;

	int x1, x2, y1, y2;
	for (int i = 1; i <= N; i++)
	{
		cin >> x1 >> y1 >> x2 >> y2;
		v[i].push_back({ x1,y1 }); 
		v[i].push_back({ x2,y2 });
	}

	// 자기자신을 부모로 지정
	for (int i = 1; i <= N; i++)
		parent[i] = i;

	for (int i = 1; i <= N; i++)
	{
		for (int j = i + 1; j <= N; j++)
		{
			bool state = check(v[i][0], v[i][1], v[j][0], v[j][1]);

			if (state == true) // 두 선분이 이어져 있다면,
				union_segment(i, j); // 노드 연결
		}
	}

	for (int i = 1; i <= N; i++)
	{
		if (!visit[i])
		{
			group_num++; // 그룹 수 추가
			BFS(i); // i 노드 기준으로 연결된 노드 수 체크  

		}
	}

	cout << group_num << '\n';
	cout << seg_num << '\n';

}

 

풀이 방법

 

코드를 큰 부분으로 나눠서 보자면 아래와 같다.

1. 두 선분의 교차 여부를 알려주는 check 함수와 CCW 함수.
2. 노드의 부모를 찾고 두 노드를 연결해주는 find_parent 함수와 union_segment 함수.
3. 연결된 노드수를 판별하는 BFS 함수.

 

풀이 방식은 선분 개수가 3000개밖에 되지 않으므로 이중 for문을 통해 모든 선분들의 교차 여부를 파악하고 교차된다면 두 선분을 연결시켜준다. 쉽게 하기 위해서 첫 번째 선분은 노드 1, 두 번째 선분은 노드 2,...... 이런 식으로 생각하면 된다.

위의 명령을 거치게 되면 각 노드의 연결관계를 알 수 있게 되는데 1~N번 노드모두 BFS로 탐색해서 이미 방문한 노드는 방문 표시를 해가며 그룹 수를 체크하고 각 그룹에서 계산된 선분 개수들 중 가장 큰 값을 저장하여서 출력하였다.

 

 

 

www.acmicpc.net/problem/2162

2162번: 선분 그룹