[platinum3][풀이미확인, 분류확인]32115 돌 놓기 게임 (체감 : 플레1 ~2)

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

 

 

아무리 봐도 플레3은 아닌 문제였다. 아이디어 발상도 흔하지 않아 떠올리기 어렵고, 구현도 내 기준 쉽지 않았다.. 

게임이론에서 쓰이는 이상한 알고리즘이 있는데 그 알고리즘이면 안 푸려고 분류를 확인하였다.. (보면서 얼떨결에 그리디라는 것도 알게 되어 큰 힌트가 된듯)

위와 같은 경우를 생각해보자. (초록색: 점수 검정색: 흑or백) 

흑 과 백이 번갈아 가며 자기의 색깔과 인접한 빈칸에 둘때 다음과 같은 생각은 어렵지 않게 할 수 있다.

 같은 색깔이 둘러싸고 있는 구간은 다른 색깔이 침범할 수 없다.

위와 같이 묶인 그룹에는 다른 색깔이 침범할 수 없다.  예를 들어 2번 그룹 (백으로 둘러싸임)에 흑이 들어갈 수 없다. 백은 백끼리 흑은 흑끼리 인접하면서 확장해 나가야 하기 때문. 

그럼 위의 그룹들 안의 0을 채워넣는 것은 가장 나중에 해도 될 것이다. 1번과 2번의 영역 싸움을 하지 않아도 되기 때문이다.

 

그렇다면 우리가 고민해야 할 부분은 다음 부분들이다.

빨간 부분들은 이제 흑과 백이 자리 선점을 위해 치열하게 경쟁하는 구간이 될 것이다.

이제 진짜 어려운 문제는 위와 같은 구간에서 어떻게 백과 흑이 최선을 다해 점수를 획득하게 하느냐 이다.

우선 직관적으로 생각해보자. 2번 구간에서 흑이 가장 쉽게 먹을 수 있는 점수는 2,14,10,12,8 점 순이다.

 즉 오른쪽에서 멀어질 수록 먹기힘든 점수가 된다.  그런데 만약 먹기 힘든 점수인데 그 점수가 매우 크다면?  위험을 무릅쓰고 라도 점수를 먹으러 갈 것이다.

흑 부터 시작하므로 , 일단 흑이 먹어야 할 점수는 3번구간의 15점이라는 것은 당연하다. 15점은 가장 큰 수이고, 지금 안먹으면 백에게 빼앗기기 때문이다. 

 그럼 흑은 일단 15점을 먹었고, 다음 턴에 백은 1번구간, 2번구간 중 어디에 두어야 할까?   2번에 두어야 할 것 같다. 지금 2번에 두게되면, 10점은 확정적으로 먹을 수 있게 된다. 아래와 같은 순서대로 결국 백이 10점을 먹게 된다. 

 

그렇다면, 구간의 딱 중간을 먹기 위해서, (10점)  먼저 돌을 두면 되겠구나! 생각이 든다.

 

그러나 또 한편으론 의심이 든다. 일단 10점을 먹기 위해서 8점부분에 돌을 두긴 두었는데,  10점으로 가는데, (8점 -> 12 점 -> 10점) 먹는 점수보다, 다른 구간을 먼저 선점하는게 이득일 수도 있지 않을까?  

예를 들면 다음과 같다.

위와 같은 경우에 백이 10점을 먹기위해 8점 -> 12점 -> 10점을 먹는 것보다  아래구간의 20점 -> 20점 을 먹는게 이득 아닌가?

그러나 그렇지 않다.  아래의 20점  구간은 안전지대로, 아직 백의 것이 확정인 상태이다. 즉 , 흑이 20점을 먹기위해 공격이 들어오면(흑이 초록5번에 두면) 그 때 백도 공격에 나서면 된다.(초록1에 둔다).

 

현 상황에서, 구간의 갯수가 홀수 일때 백이 먼저 돌을 둠으로써 자기의 영역이 된다고 확정지을 수 있는 구간은 중간 부분이다. (10점) .  그렇다면, 여러 구간들에서 중간부분의 점수를 구하고, 점수가 큰 부분부터 흑과 백이 번갈아가며 차지하려 할 것이다.

위와 같이 말이다. (구간길이가 1인 경우는 중간이 곧 구간)

 

그렇다면 구간의 갯수가 짝수인 경우는 어떻게 할까?

아래와 같은 경우를 생각해보자.

 

그렇다면 다음과 같은 과정을 겪게 될 것이다. (흑 : 파랑 , 백: 빨강)

우선 흑은 4점짜리에 먼저 둔다고 치자. 그 이유는, 다음 턴에 백이 1점에 두게 되지 않으면  흑이 21점을 먹을 수 있기 때문이다.

이제 백은 방어하기 위해 1점에 두게 된다. 

 그 다음 마찬가지 이유로 다시 흑이 20점에 두게 되고, 백은 방어를 위해 21점에 두게 된다.

이와 같은 식으로 반복하면,  짝수인 구간에서는 정확히 영역이 반으로 나뉘게 된다. (명쾌하다)

짝수인 경우에, 누가 먼저 두느냐에 따라 선점할 수 있는 구간이 없고 (구간의  절반인 구간이 홀수와 달리 없기때문) 공격이 들어오면 충분히 방어할 수 있기 때문이다.

 

그렇다면 결론적으로, 구간 길이가 홀수 인경우에 , 중간인 부분을 먼저 돌을 둠으로써 선점하면, 그 다음구간은 짝수가 되므로, 무조건 반으로 나뉘게 된다. 이해가 쉽게 그림으로 보자.

백의 차례에서 백이 가장 먼저 돌을 두면, 나머지 구간 (12, 10 , 14 ,2 ) 은 길이가 짝수가 되므로, 그다음부터는 백과 흑의 영역이 정확히 반으로 나뉘게 된다. 

 

그럼 이제 짝수구간이 되면 알아서 반반으로 나뉜다는 걸 알았으니, 어떻게 하면 되겠는가?

 

구간 길이가 홀수인경우에만, 가운데 부분이 큰 순서대로 서로 선점해 나가면 될 것이다. 위의 경우, 백이 먼저 돌을 둠으로써 , 10 점 부분이 백의 영역이 된 것처럼 말이다.

 

 

결론적으로,  빈 구간은 다음과 같이 채워질 것이다. (파란점 흑 , 빨간점 백)

 

또 그 이후 파란 구간 ( 같은 돌로 둘러싸인 구간은 알아서 같은 돌로 채워짐) 도 채운다.

 

이제 다 채웠다. 

요약하면 다음과 같다.

 

1. 1번과 2번이 대치하는 구간을 찾기.

2.  그 구간의 길이가 홀수이면, 우선순위큐에 가운데 값을 넣는다. 짝수라면, 절반 씩 구간을 채운다.

3. 우선순위큐에서 꺼내가면서, 흑백흑백흑... 순서로 가운데 값이 큰 구간부터 돌을 채우고, 구간의 나머지 부분은 짝수가 되므로, 절반씩 구간을 채운다.

4. 나머지  구간( 같은 돌로 둘러싸인 구간) 은 같은 돌로 채운다.

 

구현도 결코 쉽지 않으며, 아이디어도 어려웠는데 왜 플레3인지 의문을 가지며, 글을 마친다.