[platinum4] [해설, 분류 미확인] boj 3043 장난감 탱크

 

마치 체스판에서 룩 배치하는 느낌의 문제였다. N이 크므로 비트마스킹으로는 못풀고, 애드훅으로 해결하였다.

N*N 칸에서 N개의  탱크를 모든행과 모든열에 존재하도록 배치하는 것이, 각 행과 열에 탱크가 하나씩 있는 모양이 된다.

 

 

이 문제를 해결하기 위해, 가장 중요한 아이디어는 일단 모든열에 탱크가 존재하도록 L or R로 탱크를 이동시켜 가며 배치한 후, U or D로 탱크를 이동시키며 모든 행에 탱크가 존재하도록 하는것이다. 왜 이런 방법이 되는 것일까?

 

아래와 같은 예시를 보자.

 

맨 왼쪽에서  임의대로 배치해 모든 열에 탱크가 존재하도록 배치한 것이 두 번째, 세 번째 그림이다.  

두번째 , 세번째 그림의 상태에서 모든 행에 탱크가 존재하도록 위, 아래로만 배치한다면 그 최소 시행 수는 같다. 잘 살펴보면  위에 경우 좌우로만 탱크를 움직였기 때문에 각 행마다 존재하는 탱크의 수는 같다. 

그럼 이제, 각 행마다 탱크의 수가 같다면,  위아래로 배치할 때 최소시행수가 같은 이유를 설명해야 한다.

이유를 설명하기 전에, 한가지를 짚고 넘어가고자 한다.

처음에 다음과 같이 있고, 우선 좌우로 움직어 모든열에 존재하도록 배치한다고 생각하자.

각열마다 탱크는 하나씩 있어야 한다.

 1열부터 생각하면 여기에는 탱크가 3대 있으로 1대만 남기기 위해서는 탱크 2대를 오른쪽으로 옮겨야 한다.이때

1행의 탱크를 오른쪽으로 옮기려면, (1,3) ,(1,2),(1,1)의 탱크를 차례로 오른쪽으로 옮겨야한다.(탱크는 같은 자리에 있을 수 없기 때문). 반면, (2,1) (3,1) 의 탱크는 그냥 1대만 오른쪽으로 옮기면 된다.

 

그럼 2,3행을 옮겨야 탱크의 움직임을 최소화 할수 있을까? 

답은 1~3행의 탱크들 중 어떤 걸 오른쪽으로 옮겨도 상관없다.

만약 (3,1)탱크를 오른 쪽으로 옮긴다고 해보자. 그럼 2열에는 탱크가 2개 존재하게 되므로, (1,2) or (3,2)중 한개를 옮겨야 한다.

(1,2)를 옮기면 , (1,3)탱크도 옮겨야 한다. 

 

반면 (1,1) 탱크를 오른쪽으로 옮긴다 생각해보자.

위와 같이 동일하게 3번 옮겨야 되는걸 확인 할 수 있다.즉 (1,1)(2,1)(3,1)중 어떤걸 옮기든 2열에서 탱크가 2대가 되게 되고, 1대를 오른쪽으로 옮기고, 그러면 3열에서도 2대가되므로 1대ㄹ를 연쇄적으로 옮겨야 한다. 

즉 여기서 , 우리는 좌, 우로 움직일때는 각 열마다 탱크가 몇대있는지 중요하고, 열마다 어떤 행에 탱크가 존재하는지는 별로 중요하지 않다.(최소 움직인 횟수를 따질때)

 

 마찬가지로, 위, 아래로 움직일때는 각 행마다 탱크가 몇대있는지가 중요하게 될 것이다.  그런데, 좌우로 움직일때는 각 행마다 탱크의 수를 변화시키지 않는다.   

 따라서 먼저 좌우로 움직여 모든 열에 탱크가 차도록 하고, 그 후  위아래로 움직여 모든 행에 탱크가 차도록 하는것이 가능하다.

 

그럼 이제 실전으로 넘어가서 아래의 경우 다음과 같이 하면 된다.

1열은 탱크한 대가 있으니 pass , 2열은 (1,2) or (2,2)중 한개를 옮긴다.  여기서는  (1,2)를 옮긴다.

 

5열은 탱크가 비는데, 이때의 의 경우는 오른쪽에 위치한 탱크중 가장 가까운 탱크, 위의 경우 (3,6)의 탱크를 왼쪽으로 옮긴다. 1~4열의 탱크들은 모두 한대씩만 존재하므로, 당연하지만 움직일 수 없다.

6열도 마찬가지로, 6열의 오른쪽에 존재하는 탱크중 가장 가까운 탱크, (2,7) (3,7) 중 한개를 선택한다.

 

결과로 위와 같이 된다. 이제 위아래로 움직여 모든행에 탱크가 존재하도록 만든다.

결과적으로 위와 같이 된다.

 

 

이걸 구현하기 위해 나의 경우, L R로 움직일 때는 열이 비었을 경우, 오른쪽 걸 가져오기 위해 TreeSet을 사용, 열을 순회하면서 열에 있는 탱크를 큐에 넣어주고 큐의 크기가 1이될때까지 (탱크가 1대남을때까지) 2차원배열의 탱크를 오른쪽으로 한칸씩 옮겼다.

 

 

아이디어는 그렇게 어렵진 않았지만, 구현이 다소 까다로웠다.