전갈 그래프 판별하기

일전에 Coder's High 2016에 전갈 그래프에 대한 문제를 출제한 적이 있었다. 문제 전갈 그래프에 대한 이론적 뒷배경에 대해서는 위키백과 참고.

개인적으로 꽤 애착이 가는 문제인데, 사실 저 문제를 general case에서 해결하는 방법은 오랫동안 모르고 있었다. 고민을 했는데 못 풀고 결국은 관련 자료를 봤다. 재미있는 알고리즘이여서 공유하려고 한다.

그래프의 모든 정점의 degree에 대해서 생각을 해보자. 가시의 degree는 1이고, 꼬리의 degree는 2이고, 몸통의 degree는 n-2이고, 나머지 정점의 degree는 1 ~ n-3이다. 

이제 아무 정점이나 잡은 후, degree에 따라서 케이스를 나누자. d = 1, d = 2, d = n-2일 경우에는 몇가지 케이스를 해결하면 5n 안에 모두 문제를 해결할 수 있다. (생략한다) 3 <= d <= n-3인 경우가 문제인데, 이 경우 만약 가시가 존재한다면 다음과 같은 알고리즘으로 무조건 가시를 찾을 수 있다.

 * 자신과 연결된 정점을 A, 자신과 연결되지 않은 정점을 B라고 하자. 스택에 A와 B를 저장한 후, |A| >= 1 && |B| >= 1일 때까지 다음 과정을 반복한다.

  - 만약 A.top()과 B.top()이 연결되어 있다면, B에서 pop한다.

  - 연결돼있지 않다면 A에서 pop한다.

만약 그래프가 전갈이라면, |A| = 0이 되며, B.top()이 가시이다. A에는 몸통이나 발만이 들어갈 수 있고, B에는 가시, 꼬리, 발 만이 들어갈 수 있다. 이유를 분석하기 위해서, 전갈 그래프에서 이들의 연결 관계를 훑어보자.

 * 몸통 - 가시는 연결 돼있지 않다.

 * 발 - 가시는 연결 돼있지 않다.

 * 발 - 꼬리는 연결 돼있지 않다.

 * 발 - 발은 연결 돼있지 않을 수도 있다.

 * 몸통 - 꼬리는 연결 돼있다.

 * 발 - 몸통은 연결 돼있다.

 * 발 - 발은 연결 돼있을 수도 있다.

B에 있는 가시를 만나게 되면, A는 그 즉시 모든 원소가 사라진다. B에 있는 가시를 만나기 전에 A에 있는 모든 원소가 사라지는 경우는 존재하지 않는게, A에 존재하는 몸통을 지울 수 있는 유일한 원소는 가시 뿐이기 때문이다. 고로, d = 1인 정점을 n번의 질의로 찾을 수 있다. d = 1인 정점에서는 3n번의 질의로 전갈성을 판별할 수 있다. 고로 3 <= d <= n-3일 경우, 5n번의 질의로 문제를 해결할 수 있다.

채점 사이트 (sko)

코드