[diamond5][해설안봄, 알고리즘 분류 확인] 2323 강강술래(담력테스트..)

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

 

이번 문제는 정말 담력이 필요했던 것 같다... 나는 용기가 부족해 한참 고민하다가 결국 반신반의 하며 제출했는데 맞았다.

우선 담력을 얻을 수 있는 가장 핵심적인 부분은 제한 요소이다.

제한에서 (n - 1) (n- 2) / 2 + 2 이상이라고 했는데 왜 하필이면 이런 이상한 숫자를 제한으로 줬을 까 생각해보니, 다음과 같이 생각해볼 수 있다.

 

(n -1)*(n - 2)/2 는 nC2 로, n-1개의 점들에서 2개를 뽑는 조합이다. 즉, n-1개의 모든 점에 연결가능한 선분이 모두 연결되었다는 뜻임을 알 수 있다. 즉 빨간 원안의 점들이 여기에 속하고,  여기에 2개를 더한다는 건 이 빨간원사이 점들중 2개에 점E 을 연결한다는 것이다. 

 또 여기서 1~4들 사이의 선분들중 일부를 점 5와 연결시킬 수 있다. 즉 선분1-4 를 1-5로 변경할 수 있는 것이다. 

 

이제 각 점들마다 연결 가능한 점들의 개수를 알아보자.  A의 연결가능한 점의 수를 Pa, B의 연결가능한 점의 수를 Pb... 등이라고 하자.

 

저A는 B,C,D,에 3개, B는 A,C,D에 3개... 

이때 선분 A-D를 A-E로 옮긴다면 D는 Pd= 3,Pe=3가 될 것이다.

그러나 여기에서 어떤 점들도 2개 미만으로 될 수 없음은 금방 알 수 있다.

거기에다 한점의 연결가능한 점들수의 최소가 2개가 된다면, 나머지 점들 사이는 모두 연결되어 있을 것이다.

나머지 점들 사이가 모두연결되어있는 경우는 그냥 아무렇게나 연결해도 하나의 사이클이 되므로, (A,B,C,D) 여기에 E를 연결하면 끝난다.

 

또한 우리는 어색한 수가 어떤 경우에도 0 이된다는 것을 알 수 있다.  그 이유를 알기 위해 우선

우리가 저 모양에서 선분을 변경 가능한 개수는 끽해야 n-3개임을 알 수 있다. 일단 C,D는 모든 점과 연결되어 있으므로  선분을 이동할 수 없고. E는 E-C -> E-A로 옮겨봤자 똑같은 모양이 나온다는 것을 알 수 있기 때문에 E도 선분을 이동할 수 없다.   A,B에서는 A-D -> A-E ,  B-C -> B-E 이렇게 이동이 가능하다.

그런데 어색한 수가 나오려면

 

이런식으로 사이클이 아예 분리가 되어야 한다. 

저 삼각형 사이클을 살펴보자. 원래 분리되기 전에는 한 점마다 n개에 근접한 외부의 (사이클에 포함되지 않은)선분이 연결되어 있었을 것이다. 아니면 설령 한점이 Ppoint = 2 라고 해도  나머지 점들은 Ppoint = n - 2 일 것이다. 따라서  3개의 점에 연결된 선들을 합치면 무조건 n개가 넘어가는데 이 선들을 이동시켜야 분리된 사이클이 가능하다. 그러나 방금전 n-3개까지 선분이 이동가능하다고 하였으므로 사이클을 분리시키는 것은 불가능 하다.

 

그럼 이제 어색한 수가 무조건 0이된다는 것을 알았다. 즉 모든 점들이 하나의 사이클이 된다는 것을 알았다.

그렇다면 이제 어떻게 이 점들을 이을지 고민해 봐야할 것이다.

 

 

만약 E부터 시작한다고  하면 E-D-C-A-B 로 연결한다고 하면 B에서 갈 곳이 없어 (연결된 선분의 개수가 0)  B에서 E로 연결이 불가능하다.  그렇다면 연결된 선분수가 가장 적은 점부터 차례대로 연결하면 되지 않을까?  Ppoint가 작은 순으로 그리디하게  연결하면 Ppoint = 0 이 되는 부분 없이 다 연결이 가능할 것같기도 하다. 물론 이건 여기서 각 점들마다 Ppoint가 충분히 크다고 가정했을 때이다. Ppoint의 최소는 2이고, 나머지들은 3이상이므로.

A에서 시작하면 이제 A는 이미 방문했으므로  Pb = 3- 1 = 2(A,C,D 에서 A삭제), Pc = 4 - 1 = 3, Pd = 4- 1 이 되고, 여기서 제일 작은 B로 간다. B로 가면 똑같이  Pc = 2, Pd = 2 , 이고 (A는 방문했으므로 skip) 여기서는 아무데나 간다. C로 가면 Pe = 1, Pd = 1 이 된다. 여기서 E로 갔다가 D로 간후 다시 A로 돌아오면 끝난다. 

 

 

 

상상을 해보았을 때 충분히 가능할 것 같은데.. 일단 불안 센서에 감지된 문제는 2가지가 있다.

1. 그리디 하게 Ppoint를 줄여가다가 고립될 경우(사이클안에 갇힐 경우).

즉 만약 Ppoint 를 줄여나가며 작은 것부터 이어나가다가 

 

화살표 방향으로 들어가버리면 안에서 고립된채 다른 선들과 연결하지 못하고 끝날 것이다.

그런데 이런 경우는 일어나지 않는다. 저렇게 고립된 사이클이 형성되려면 외부의 연결가능한 점들이 모두 없어져야 하는데  그 말은 이미 외부의 점들은 모두 연결이 되어있다는 것이다. 즉 저 사이클만 연결되면 모든 점들과 연결이 되는 것이다.

 

 

 

2. 그리디하게 Ppoint가 작은 점부터 먼저 연결한다고 해도, 다시 출발점으로 못돌아오는 경우

 

이 경우를 해결하기 위해 Ppoint를 가장 큰 부분을 출발지로 두면 되겠다는 생각이 들었다. 그러면 마지막 점까지 연결되어있을 때,  그 점이 출발지와 연결되어있을 가능성이 크기 때문이라고 생각했다.

 

잘 살펴보면 Ppoint의 최댓값이 될 수 있는 값들은 n - 1 or n- 2 라는 것을 알 수 있다.  n-1일 경우는 다른 모든 점들과 연결된 경우이고, n-2일 경우는 한점만 제외하고 모두 연결된 경우이다.Ppoint가 n-2보다 작아질 수는 없다. 왜냐하면 선분들은 n-3개만 이동이 가능한데, n- 1개의 점들중 2개는 Ppoint = n - 1, 나머지는 Ppoint = n- 2인데,      여기서 n-3개를 줄여봤자 나머지 2개의 점은 n-1 or n-2가 될 것이다.

 

Ppoint의 최댓값이 n- 1이고 start지점으로 지정할 때는  어떤 점으로 끝나든 모든 점들에서 start지점으로 돌아올 수 있다.

문제는 start지점의 P값이 n-2일 때이다. 한점만 빼고 모두 연결되었는데 만약 연결되지 않은  점으로 끝나면 start로 돌아올 수 없다. 그렇다면 여기서는 이 연결되지 않은 점을 우선적으로 처리하면 나머지 점은 어떻게 끝나든 start로 돌아올 수 있다.

여기서 내가 생각한 아이디어는 연결되지 않은 그 점이 A라고 치면, A와 연결된 모든 점들 중 가장 Ppoint값이 작은 값을 찾는다.(C라고 하자) 사실 A와 연결된 모든 점들은 start 와 연결이 되었으므로,(start는 A제외 모든 점과 연결되어있으므로) C또한 start와 연결되어 있을 것이다.

그러므로 start ->C -> A 순으로 이어나가면, 이제 어떤점으로 끝나든 start지점으로 돌아올 수 있게 된다.

 

정리하면 이렇게 된다.

 

1. Ppoint값이 가장 큰 점을 start로 한다.

2. 그 때의 Ppoint가 n-2일 때만 연결되지 않은 한 점A를 찾고 C를 start와 연결한다. 

3. 그 후로는 Ppoint가 작은 값부터 우선적으로 마지막 까지 연결해 나간다.

 

이렇게 직관적으로는 간단하지만, greedy drawer같은 문제에서 예외처리에 고통을 받은 나로서는 상당히 의심이 가는 문제였다고 할 수 있다... 일단 논리적으로 저렇게 생각하고 일말의 자신감을 얻고 코드를 제출했는데 맞아서 정말 다행이다.

난이도 기여를 살펴보니 Ore정리에 의해 해밀턴 경로가 존재한다고 하는데...  증명이 된 문제였나 보다.