20040. 사이클 게임

20040번: 사이클 게임

---

문제 이해

문제 설명에서 헷갈리기 쉬운 부분을 정리한다.

• 평면 상에 점 $n$개가 주어지는데, 이 중 어느 세 점도 일직선 위에 놓이지 않는다.

평면 위의 점이 주어진다고 한다. 그런데 점의 좌표가 없다. 이게 뭐지? 하고 당황할 수 있지만 두 번째 조건이 중요하다. 어느 세 점도 일직선 위에 놓이지 않는다고 한다. 좌표가 주어지지 않았지만 대략 이런 형태의 모양을 상상할 수 있다. 바로 정$n$각형이다. 정$n$각형의 꼭짓점은 위의 조건을 정확히 만족한다.

• 사이클

사이클의 정의를 명확하게 알아야 한다. 단순히 선분이 교차한다고 해서 사이클이 되지는 않는다. 조건을 자세히 읽어보자.

 

C에 속한 임의의 선분의 한 끝점에서 출발하여...

 

따라서 그냥 정점만 가지고도 사이클 여부를 판단할 수 있다. 복잡한 기하 공식을 생각하지 않아도 된다.

해결

점의 개수 $n$이 최대 $500,000$이기 때문에,

1. 사이클 여부를 확인할 때 그래프를 탐색해서는 안 된다. 
2. 그래프를 인접 리스트로 표현하는 것이 의미가 있는지 잘 모르겠다.

2번이 중요하다. 진행된 차례 $m$이 최대 $1,000,000$이라서 메모리 초과가 나지는 않겠지만, 사이클 여부를 판단하기 위해 인접 리스트가 필요한지 고민해 봐야 한다. 결론을 말하자면, union-find 알고리즘으로 문제를 해결할 수 있다. 인접 리스트로 간선을 저장하는 대신, union-find로 부모-자식 관계만 알면 된다. 

 

사이클이 처음으로 발생할 때 union-find에서는 어떤 일이 일어날까? 예제 입력 2번을 통해 알아보자.

예제 입력 2

다음과 같이 평면 위에 6개의 점이 존재한다. 위에서 말했듯이 문제의 조건을 만족하는 가장 간단한 모양은 정$n$각형이다.

정육각형이라고 치자

1번째 차례에서 0번과 1번 정점이 연결된다. 나는 부모의 번호가 더 작은 쪽으로 union하도록 구현했다. 따라서 1번 정점의 부모는 0번이 된다.

차례 1

2~3번째 차례에서도 마찬가지로 정점이 연결된다. 아직 사이클은 나타나지 않았다.

차례 3이 끝난 후

차례 4에서는 0번과 3번 정점이 연결된다. 이때 사이클이 최초로 발생한다.

사이클!

위에서 간선(그래프) 대신 정점(union-find)에 집중하자고 했다. 사이클이 발생할 때 0번과 3번 정점을 자세히 살펴보면 한 가지 흥미로운 사실을 알 수 있다.

 

두 점은 이미 연결되어 있었다.

 

3번 정점은 차례 3에 의해 0번의 자식 정점이 되었다. 문제에서 같은 선분이 두 번 이상 주어지는 경우가 없다고 했으므로, 이미 연결되어 있는 두 정점을 또 다시 연결하면 사이클이 생길 수밖에 없다. 

정리

주어진 간선이 연결하는 두 정점의 부모가 이미 같다면 사이클이 발생했음을 알 수 있다. 정점을 연결하면서 두 정점의 부모가 이미 같은지 확인하면 된다.

---

이 문제를 마지막으로 solved.ac 클래스 5의 모든 문제를 해결하였다.