문제
3*3 표에 다음과 같이 수가 채워져 있다. 오른쪽 아래 가장 끝 칸은 비어 있는 칸이다.
| 1 | 2 | 3 |
| 4 | 5 | 6 |
| 7 | 8 |
어떤 수와 인접해 있는 네 개의 칸 중에 하나가 비어 있으면, 수를 그 칸으로 이동시킬 수가 있다. 물론 표 바깥으로 나가는 경우는 불가능하다. 우리의 목표는 초기 상태가 주어졌을 때, 최소의 이동으로 위와 같은 정리된 상태를 만드는 것이다. 다음의 예를 보자.
| 1 | 3 | |
| 4 | 2 | 5 |
| 7 | 8 | 6 |
| 1 | 2 | 3 |
| 4 | 5 | |
| 7 | 8 | 6 |
| 1 | 2 | 3 |
| 4 | 5 | |
| 7 | 8 | 6 |
| 1 | 2 | 3 |
| 4 | 5 | 6 |
| 7 | 8 |
가장 윗 상태에서 세 번의 이동을 통해 정리된 상태를 만들 수 있다. 이와 같이 최소 이동 횟수를 구하는 프로그램을 작성하시오.
입력
세 줄에 걸쳐서 표에 채워져 있는 아홉 개의 수가 주어진다. 한 줄에 세 개의 수가 주어지며, 빈 칸은 0으로 나타낸다.
출력
첫째 줄에 최소의 이동 횟수를 출력한다. 이동이 불가능한 경우 -1을 출력한다.
소스
import java.util.*;
public class Main {
static int[] dx = {0,0,1,-1};
static int[] dy = {1,-1,0,0};
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
int start=0;
for(int i=0;i<3;i++)
for(int j=0;j<3;j++) {
int temp=scan.nextInt();
if(temp==0) temp =9;
start=start*10+temp;
}
Queue<Integer> q = new LinkedList<Integer>();
HashMap<Integer,Integer> d = new HashMap<Integer,Integer>();
d.put(start, 0);
q.add(start);
while(!q.isEmpty()) {
int now_n = q.poll();
String now = Integer.toString(now_n);
//1 0 3
//4 2 5
//7 8 9
int z = now.indexOf('9');//빈칸 위치 저장
int x = z/3; //x좌표 계산
int y = z%3; //y좌표 계산
for(int k=0;k<4;k++) {
int nx=x+dx[k];
int ny=y+dy[k];
if(nx>=0&&nx<3&&ny>=0&&ny<3) {
StringBuilder next = new StringBuilder(now);
char temp = next.charAt(x*3+y);
next.setCharAt(x*3+y, next.charAt(nx*3+ny));
next.setCharAt(nx*3+ny,temp);
int num=Integer.parseInt(next.toString());
if(!d.containsKey(num)) {
d.put(num,d.get(now_n)+1);
q.add(num);
}
}
}
}
if(d.containsKey(123456789)) System.out.println(d.get(123456789));
else System.out.println(-1);
}
}