문제 설명
3*3크기의 배열로 표현된 8퍼즐의 초기 상태와 목표 상태가 주어질 때
초기상태에서 목표상태로 이동하는 단계의 수를 계산해보자. 단계의 수란 상태의 변화가 몇 번 이루어졌는가를 나타내는 수이다.
예를 들어 8퍼즐의 초기 상태와 목표 상태가 다음과 같을 때 초깃 상태를 1로 두고 1번의 이동으로 6을 아래로 내리는 한번의 이동으로 목표 상태가 나타나기 때문에 단계의 수는 1이다.
2 8 3 2 8 3
1 6 4 1 0 4
7 0 5 7 6 5
초기 목표
* 8퍼즐은 1~8까지의 숫자를 이동하여 목표 상태로 만들어 내는 것으로 빈칸은 0으로 표현한다.
초기상태에서 목표상태로 이동하는 단계의 수를 계산해보자. 단계의 수란 상태의 변화가 몇 번 이루어졌는가를 나타내는 수이다.
예를 들어 8퍼즐의 초기 상태와 목표 상태가 다음과 같을 때 초깃 상태를 1로 두고 1번의 이동으로 6을 아래로 내리는 한번의 이동으로 목표 상태가 나타나기 때문에 단계의 수는 1이다.
2 8 3 2 8 3
1 6 4 1 0 4
7 0 5 7 6 5
초기 목표
* 8퍼즐은 1~8까지의 숫자를 이동하여 목표 상태로 만들어 내는 것으로 빈칸은 0으로 표현한다.
입력 설명
초기상태 3*3 배열과 와 목표 상태 3* 3 배열이 순서대로 입력된다.
숫자는 공백으로 구분이 되며 빈칸은 0으로 표현된다.
숫자는 공백으로 구분이 되며 빈칸은 0으로 표현된다.
출력 설명
초기상태에서 목표 상태로 도달하는 최소한의 단계 수를 출력한다.
입력 예시 Copy
2 8 3
1 6 4
7 0 5
1 2 3
8 0 4
7 6 5
출력 예시 Copy
5