2639번 - 주차장 스페셜 저지채점 준비 중

<그림 1>과 같이 정사각형 NxN 크기의 주차장이 있다. 이 주차장에는 차들이 많이 있는데, 우리 차를 주차장 밖으로 빼내어야 한다. 그런데 차를 움직일 수 있는 주차관리원은 한 명 뿐이다. 이 주차관리원이 하나의 차를 타고 그 차를 움직이는 것을 하나의 “작업”이라 부르기로 한다. 하나의 작업에 차는 앞뒤로 다른 차와 겹치지 않는 한 얼마든지 움직일 수 있다. 다음의 가정 하에 작업의 횟수를 가장 적게 하면서 우리 차를 주차장 밖으로 빼내기 위해서 움직여야하는 모든 차들의 순서를 계산하는 프로그램을 작성하시오. 답이 여러 가지가 나올 수 있는 경우에는 그 중 하나만 출력한다.

가정

1. 모든 차의 폭은 1이고, 길이는 2 또는 3 이다.
2. 차는 주차되어 있는 방향에 따라 수직차(예:<그림 1>의 4번차), 수평차(예:<그림 1>의 3번차)로 구분한다. 수직차는 상하로만, 수평차는 좌우로만 움직일 수 있고 회전은 할 수 없다.
3. 같은 차에 대해서 여러 번 작업할 수 있다.
4. 우리 차 외에 다른 차는 작업 도중 조금이라도 주차장 밖으로 나갈 수 없으며, 우리 차가 완전히 주차장을 나가는 순간에 전체 작업은 끝난다(<그림 2>).
5. 우리 차가 수평차라면 오른쪽으로만 주차장을 나갈 수 있고, 수직차이면 위쪽으로만 나갈 수 있다.
6. 입력 데이터에서 우리 차는 반드시 주차장을 빠져 나갈 수 있도록 되어 있다.

<그림 1> 초기 주차장의 모습

<그림 2> 우리 차를 빼낸 후의 주차장의 모습

첫째 줄에는 주차장의 크기를 나타내는 정수 N (3 ≤ N ≤ 15), 다음 N 개의 줄에는 각각 N 개의 숫자가 한 칸씩 띄어서 나타나는데 0은 빈 공간을 뜻하고, 1은 우리 차를 뜻하며, 나머지 차에는 2부터 연속된 정수가 각각 부여된다.

첫째 줄에는 총 작업의 횟수를 나타내는 정수 K를 출력한다. 다음 K 줄은 진행된 작업을 순서대로 출력한다. 한 줄이 한 작업을 나타내며 두 개의 정수로 이루어진다.

첫째 정수는 움직인 차의 번호, 둘째 정수는 움직인 거리를 나타낸다. 단, 거리는 격자의 개수를 의미한다. 수평차인 경우 오른쪽 방향으로 움직인 거리를 양의 정수, 왼쪽 방향으로 움직인 거리를 음의 정수로 나타낸다. 수직차이면 위쪽 방향으로 움직인 거리를 양의 정수, 아래쪽 방향으로 움직인 거리를 음의 정수로 나타낸다.