BOJ 18785 : Clock Tree

https://www.acmicpc.net/problem/18785

18785번: Clock Tree

상당히 어려운 문제였다..

 

먼저 우리는 이러한 통로를 가면서 맞춰놓을 때, 처음 노드에서 출발해서 다시 돌아오는 방식임을 알 수 있다.

 

이때 왔다갔다 하면서 관찰할 수 있는 건 어떤 노드와 그 주변 노드가 하나 있을 때 둘 다 자신을 다 12시로 맞추기 위해서는 자신과 1차이나는 노드가 항상 있어야 한다는 거다. 

 

그리고 항상 인접한 노드들끼리만 시간에 영향을 준다.

 

그렇다면 이 사실들을 이용해서 노드가 여러 개일때를 살펴보자. 먼저 시작노드를 기준으로 해서 거리가 홀수인 그룹과 짝수(혹은 0)인 그룹으로 나누자.

 

그룹 안 노드들은 서로에게 영향을 주지 않는다. 그리고 한 번 건너갈 때마다 각 그룹마다 필요한 시간들이 번갈아가면서 1씩 줄어들게 된다.

 

그러면 두 그룹에게 필요한 시간이 얼마나 차이나냐에 따라 시작정점의 개수가 정해진다.

 

1) 두 그룹의 필요한 시간이 같을 때 : 모든 곳이 될 수 있다.

2) 두 그룹의 필요한 시간의 차이가 1일 때 : 짝수 그룹이 더 크다면 짝수 그룹의 노드 개수, 아니면 홀수 그룹의 노드 개수이다.

3) 그 외 : 가능한 노드가 없으므로 답은 0이다. 

 

코드