주차장 > 문제은행

본문 바로가기


문제은행

1010 : 주차장

제한시간: 1000 ms    메모리제한: 256 MB
해결횟수: 4 회    시도횟수: 98 회   



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

 

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

 

e3050b66a1b29a01767400d7560a4131_1449735
 


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


첫째 줄에는 총 작업의 횟수를 나타내는 정수 K를 출력한다. 다음 K 줄은 진행된 작업을 순서대로 출력한다. 한 줄이 한 작업을 나타내며 두 개의 정수로 이루어진다.
첫째 정수는 움직인 차의 번호 둘째 정수는 움직인 거리를 나타낸다. 단 거리는 격자의 개수를 의미한다. 수평차인 경우 오른쪽 방향으로 움직인 거리를 양의 정수 왼쪽 방향으로 움직인 거리를 음의 정수로 나타낸다. 수직차이면 위쪽 방향으로 움직인 거리를 양의 정수 아래쪽 방향으로 움직인 거리를 음의 정수로 나타낸다.

[Copy]
6
2 0 0 6 6 6
2 0 0 8 0 9
1 1 0 8 4 9
3 3 3 0 4 9
0 0 10 0 7 7
11 11 10 5 5 0
[Copy]
8
1 1
2 -1
6 -3
8 1
4 2
7 -1
9 -2
1 5





HancomEducation E-mail : hancomc@hotmail.com, comkiwer@naver.com Tel : 070-7163-5782 FAX : 031-388-0996 정올소개 이용약관 개인정보처리방침
경기도 안양시 동안구 호계동 1065-10 협성골드프라자 601호, 경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호
Copyright@2010-2015 jungol. All right reserved.