union find 썸네일형 리스트형 2162번: 선분 그룹 - Baekjoon Online Judge 선분 그룹이라는 문제는 기하 알고리즘 문제풀이의 기초이자 꽃이라고 할 수 있는 CCW를 이용하는 동시에 유니온 파인드를 섞어 놓은 문제였다. 문제를 보면서 대충 어떤 식으로 풀면되겠다는 것이 머리 속에 그려져서 로직도 금방 세우고 코딩도 금방했는데 의외로 계속 오답이 나서 짜증나는 문제였다. 문제를 살펴보면 여러 선분이 주어졌을 때, 만일 선분끼리 교차되거나 겹치게 되면 그 선분들은 하나의 그룹이 된다. 이 때 선분들을 몇 개의 그룹으로 묶을 수 있고 그룹 중에 가장 많은 선분을 포함하고 있는 그룹에 속한 선분이 몇 개인지 출력하면 된다. 문제를 보고 생각난 것은 CCW였다. 기하 문제를 풀어본 사람은 알겠지만, CCW를 이용하면 두 선분의 교차 여부를 쉽게 파악할 수 있다. 만일 CCW가 익숙하지 않은.. 이전 1 다음