티스토리 뷰

공부

전갈 그래프 판별하기

구사과 2016. 10. 5. 22:04

일전에 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)

코드

'공부' 카테고리의 다른 글

Subset XOR Maximization  (0) 2016.10.09
(Codeforces) Intel Code Challenge Final Round  (0) 2016.10.09
전갈 그래프 판별하기  (0) 2016.10.05
유량 관련 알고리즘 정리  (10) 2016.10.03
problem solving 2016.09.24  (0) 2016.09.24
BOJ 1209 단조수열 만들기 : O(NlgN)  (1) 2016.09.15
댓글
댓글쓰기 폼
공지사항
Total
770,781
Today
415
Yesterday
1,620