[platinum4] [풀이, 해설 미확인] 33617 치터잡기

 

 

 

 

이 문제는 아이디어만 떠오르면 구현은 좀 복잡할 지라도 꾸역꾸역 어떻게든 풀 수 있는, 아이디어가 거의 전부인 문제다.

치터가 어떻게 가든 치터를 N^2 안에 잡아야 하는데, 치터는 안잡히기 위해 최선을 다해 도망다닐 거라고 생각해도 될것이다.

즉 게임이론의 성격도 가지고 있다. 그러나 그동안 메모이제이션을 통해 최선을 다할 경우를 dp나 백트래킹으로 풀었던 다른 게임이론 문제들과는 달리, 2차원 배열이기 때문에 dp , 백트래킹으로는 풀 수 없다. 결국 패턴을 찾아야 하므로, 애드훅 문제라고 할 수 있다. 

 

결론부터 얘기하면, 한번 움직일 때 N번씩 움직일 수 있다면, 한번 움직일 때마다 그동안 지나왔던 범위에 치터가 들어온 경우를 다시 점검하고 , 한칸 씩 더 클리어 영역(치터가 없는게 확실시된 영역) 을 늘릴 수 있다.

아래와 같이 N = 5 라면, 1,1부터 시작해서 1열 모두 검사하고, (5,2) 로 갈 수 있다. 즉 N칸 씩 가면 한칸 씩 영역을 넓힌다는 직관적인 아이디어를 생각할 수 있을 것이다.

 

 

 

 

이제 약간 게임이론 처럼 접근해 보자. 

파란점(나의 위치)로 올동안 파란 선을 거쳐왔는데, 치터가 발견되지 않았다면 파란선이 지나가는 격자들은 모두 치터가 없는 곳이다. 현재 나의 위치는 파란점이고,  치터가 있을 수 있는 곳은 빨간 점들 중 하나이다.

 

 

이제 치터차례에 치터가 있을 수 있는 곳은 위와 같다.

 

그럼 내가 이제 지나온 영역에 치터가 침범했을 수도 있는 곳(1,1) (2,1) (3,1) (4,1) 을 모두 재검사하면서, 나의 영역을 한칸늘릴 방법은 다음과 같다.

직관적으로 바로 보일 수도 있다. 사실 저 상황에선 유일한 방법이 있기 때문이다.

 

바로 위처럼 한번 꺾어서 검사하는 방법이다. 저렇게 지나가면 이미 검사한 영역에 침범했을 수도 있는 치터를 잡아낼 수 있을 것이다.  또 눈치챘을 수도 있겠지만, 초록색을 거침으로써 이제 치터가 침범할 수 없는 영역은 (4,1), (5,1) 두 곳이 되었다. 4행 5행에서 치터가 침범할 수 영역은 (4,2) , (5,2) 가 되었고 이 영역은 이제 꾸준히 검사하므로  치터가 (4,1), (5,1)까지 가기전에 잡을 수 있다.

이해하기 쉽게 그림으로 보자면  아래와 같이 초록 점에 내가 도착한후, 치터 차례에 치터가 있을 수 있는 곳은 아래와 같다.

 

 

 

초록색 영역 까지 가는 동안 영역에 숨어들기를 기다리는 치터의 위치는 빨간점들중 하나일 것이다.

 

 

이제 내가 5,2 에 도착했을 때 치터 위치는 왼쪽 사진의 빨간 점 중 하나일 것이고, 치터 차례에 치터가 갈 수 있는 곳은  오른쪽 사진의 빨간 점 중 한가지이다. 이제 (3,1), (4,1) (5,1)은 안전지대가 된 것을 확인 할 수 있다.

이제 이렇게 지그재그로 지나가면서 꺾는 곳을 한 행씩 높여 가면 다음과 같이  한번움직일 때마다 N번 움직이는 N번의 턴 끝에 

1열 (1,1)(2,1)(3,1)(4,1)(5,1) 은 치터가 이제 침범할 수 없는 안전지대가 되었다.

 

내가(5,2)에 있을 때 치터 위치는 왼쪽과 같고 여기서 N번움직인 후 꺾으면 오른쪽과 같다.

이제 양상은 처음과 상하로 대칭일 뿐이지 완벽히 같으므로 똑 같은 작업을 진행하면된다.

위와 같이 진행.

 

이렇게 진행하면 한열 clear시 N번의 차례가 필요하고, 1,2,3,4 열까지만 클리어 하면 아래와 같이 되므로 총 횟수는 N * (N - 1)회이다.

 

이 경우는 홀수 일때고  짝수 일때는 한 열 클리어시 홀수일때와 달리 ㄱ 자로 나오는 게 아닌 들어가는 방향 (ㄱ 쓰는 순서의 역순)으로 들어가기 때문에 한번 나와야 해서 한열 클리어시 (N + 1)번의 차례가 필요하고 , (N - 1)번 반복하므로 (N + 1) * (N - 1) =  

N ^ 2 - 1 로 N^2안에 해결할 수 있다.

 

짝수 홀수, 지그재그 의 상하 방향등을 고려해 구현하기엔 좀 까다로웠지만 , 아이디어만 떠올리면 그게 거의 전부인 ㅁ누제였다.