[BOJ] 2162 선분 그룹 (C/C++)

2162번: 선분 그룹

문제

N개의 선분들이 2차원 평면상에 주어져 있다. 선분은 양 끝점의 x, y 좌표로 표현이 된다.

두 선분이 서로 만나는 경우에, 두 선분은 같은 그룹에 속한다고 정의하며, 그룹의 크기는 그 그룹에 속한 선분의 개수로 정의한다. 두 선분이 만난다는 것은 선분의 끝점을 스치듯이 만나는 경우도 포함하는 것으로 한다.

N개의 선분들이 주어졌을 때, 이 선분들은 총 몇 개의 그룹으로 되어 있을까? 또, 가장 크기가 큰 그룹에 속한 선분의 개수는 몇 개일까? 이 두 가지를 구하는 프로그램을 작성해 보자.

입력

첫째 줄에 N(1 ≤ N ≤ 3,000)이 주어진다. 둘째 줄부터 N+1번째 줄에는 양 끝점의 좌표가 x1, y1, x2, y2의 순서로 주어진다. 각 좌표의 절댓값은 5,000을 넘지 않으며, 입력되는 좌표 사이에는 빈칸이 하나 있다.

출력

첫째 줄에 그룹의 수를, 둘째 줄에 가장 크기가 큰 그룹에 속한 선분의 개수를 출력한다.

---

어제에 이어서 푼 플레 문제. solved.ac 5클래스를 배회하다가 발견하고 충분히 풀 수 있을 것 같아 도전했다. 문제를 봤을 때 어제처럼 union-find를 사용하면 될 것 같았다. 

 

핵심은 두 선분이 교차하는지 안 하는 지를 판정하는 것이었다. 그런데 두 선분 교차 판정하는 것쯤이 야하고 도전했지만 쉽게 해결되지 않아서 구글을 참고했다. 선분 교차 판정을 위한 CCW라는 알고리즘이 있었다. 아래 블로그가 가장 친절하게 설명되어있었다. CCW 알고리즘을 이해하기는 했지만 나 혼자서는 절대 생각하지 못했을 것 같다.

선분의 교차 여부 확인

 

아무튼 CCW 알고리즘이 복잡하기는 해도 두 선분의 교차 여부를 판정하는데에는 O(1)이면 충분하다. 이때 선분 그룹을 만들기 위해서는 O(N^2)의 시간 복잡도가 필요하지만 N이 최대 3000이라서 2초 안에는 충분히 가능하다. 코드를 작성하다 보니 O(N^2)이긴 하지만 상수가 꽤나 커 보였다. N이 좀 더 커지거나 시간 제약이 타이트해지면 최적화가 필요할 것 같다. 그런데 어떤 부분을 최적화해야 큰 효과를 볼 수 있을지는 잘 모르겠다...

 

 

후기)

드디어 solved.ac 티어 플레에 입성했다. 스스로 생각하기에 플레 실력은 안돼서 돼지 목에 진주 목걸이 같은 느낌이긴 하지만 그래도 열심히 했다!

solved.ac - uyt8989