주차의 달인 택쌤은, 주차장에서 어떤 차 밑에 아기 고양이가 자고 있는 것을 목격했다.

가만히 내두면 아기 고양이가 위험하기 때문에,택쌤은 아기 고양이를 안전한 곳으로 옮기려고 한다.

아기 고양이를 구하기 위해선, 우선 아기 고양이가 위치한 공간에 있는 차를 움직여서 그 공간을 비워야 한다.

주차장에는 1x2크기의 차들이 가로 혹은 세로로 주차되어 있다.

이 주차장은 단 한 곳, 1x1크기의 빈 공간이 있으며, 이를 이용해 차들을 움직여서 새로운 빈 공간을 만들어내야 한다.

어떤 공간은 장애물이 위치하여, 아예 차가 못 움직이기도 한다.

다음 그림을 보자.

3번 차 밑에 있는 검은색 공간이, 아기 고양이의 위치이다.

고양이를 구출하기 위해선, 차 8을 움직여서 (1,1)에 빈공간을 만들고, 그 빈공간으로 다시 차 4를 움직여서 (3,1)에 빈공간을 만들고, 마지막으로 3을 움직이면 된다.

(3,4)에 위치한 X는 장애물을 뜻한다.

주차장의 상태가 주어졌을 때, 움직여야 하는 차의 번호를 순서대로 출력하는 프로그램을 작성하라.

주차의 달인 timer 1s memory 32MB

주차의 달인 1s 32MB