문제 설명
8퍼즐이란 1~8까지의 숫자를 3x3크기의 격자판에 두고 숫자를 이동시켜 1~8까지 순서대로 맞추는 퍼즐이다. 예를 들면 아래 왼쪽과 같이 흩어져있는 숫자가 게임의 초기 상태로 주어지며 오른쪽과 같이 정렬된 퍼즐로 만들어야 한다. 이러한 8 퍼즐을 컴퓨터로 해결하기 위해 모델링하게 되면 다음과 같이 표현된다.
8퍼즐은 게임을 진행하기 위해 다음과 같은 수행작업을 할 수 있다.
<수행작업>
빈칸 위에 숫자를 아래로 내리기
빈칸 왼쪽의 숫자를 오른쪽으로 옮기기
빈칸 오른쪽의 숫자를 왼쪽으로 옮기기
빈칸 아래의 숫자를 위로 옮기기
예시의 현재 상태의 경우 빈칸 위의 숫자가 없기 때문에 1번 작업은 할 수 없다.
현재상태에서 2번작업 또는 3번, 4번 작업을 수행한 결과는 각각 다음과 같다.
<현재상태->3번작업>
<현재상태->4번작업>
8퍼즐의 상태 리스트와 수행작업 번호가 주어졌을 때 다음에 나타나는 상태를 출력하시오.
<현재상태>
| 8 |
|
6 |
| 5 | 4 | 7 |
| 2 | 3 | 1 |
리스트 표현: 8 0 6 5 4 7 2 3 1 (*여기에서 빈칸은 0으로 표현함.)
8퍼즐은 게임을 진행하기 위해 다음과 같은 수행작업을 할 수 있다.
<수행작업>
빈칸 위에 숫자를 아래로 내리기
빈칸 왼쪽의 숫자를 오른쪽으로 옮기기
빈칸 오른쪽의 숫자를 왼쪽으로 옮기기
빈칸 아래의 숫자를 위로 옮기기
예시의 현재 상태의 경우 빈칸 위의 숫자가 없기 때문에 1번 작업은 할 수 없다.
현재상태에서 2번작업 또는 3번, 4번 작업을 수행한 결과는 각각 다음과 같다.
<현재상태->2번작업>
|
|
8 | 6 |
| 5 | 4 | 7 |
| 2 | 3 | 1 |
리스트 표현: 0 8 6 5 4 7 2 3 1 (*여기에서 빈칸은 0으로 표현함.)
<현재상태->3번작업>
| 8 | 6 |
|
| 5 | 4 | 7 |
| 2 | 3 | 1 |
리스트 표현: 8 6 0 5 4 7 2 3 1 (*여기에서 빈칸은 0으로 표현함.)
<현재상태->4번작업>
| 8 | 4 | 6 |
| 5 |
|
7 |
| 2 | 3 | 1 |
리스트 표현: 8 4 6 5 0 7 2 3 1 (*여기에서 빈칸은 0으로 표현함.)
8퍼즐의 상태 리스트와 수행작업 번호가 주어졌을 때 다음에 나타나는 상태를 출력하시오.
입력 설명
첫 번째 줄에 8퍼즐의 상태 9자리 수가 입력된다.
두 번째 줄에 수행작업 번호가 입력된다.
두 번째 줄에 수행작업 번호가 입력된다.
출력 설명
수행작업이 수행된 다음 상태를 출력한다.
만약 수행작업의 수행이 불가능 하면 ‘x’를 출력한다.
만약 수행작업의 수행이 불가능 하면 ‘x’를 출력한다.
입력 예시 Copy
8 0 6 5 4 7 2 3 1
1
출력 예시 Copy
x