문제 : https://www.acmicpc.net/problem/1525

Key Point
8 퍼즐 문제이므로 9!개의 경우의 수가 있다.
그리고 0 -> 9로 바꿔서 9자리의 수가 나오므로 이를 이용해서 문제를 푼다.
네 방향으로 이동할 수 있다.

Explain
큐를 이용해서 값을 꺼내면서 찾는다.
그리고 Map을 이용해서 상태 값을 저장한다.
큐에 있는 값들을 빼면서 가장 적게 걸리는 상태를 찾아낸다.
모든 경우의 수를 탐색하면서 상태값을 저장하고 원하는 123456789의 상태값만 찾아서 출력하면 된다.

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
public class Exam1525 {
	
	public static final int[] dx = {0,0,1,-1};
	public static final int[] dy = {1,-1,0,0};
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n=3;
		int start=0;
		for(int i=0;i<n;i++) {
			for(int j=0;j<n;j++) {
				int temp = sc.nextInt();
				if(temp == 0) {
					temp =9;
				}
				start = start*10 + temp;
				// 숫자를 문자열처럼 저장하기 위함
				// 그리고 2차원 배열의 형태를 1차원 배열의 형태로 바꾸기 위해서
			}
		}
		Queue<Integer> q = new LinkedList<Integer>();
		Map<Integer, Integer> map = new HashMap<Integer, Integer>();
		map.put(start, 0);
		q.add(start);
		while(!q.isEmpty()) {
			int now_num = q.poll(); // 제일 위에 있는 숫자 빼
			String now = Integer.toString(now_num); // 숫자를 문자열로 변환
			int z = now.indexOf('9'); // 그리고 9[0]이 있는 위치를 찾는다. 
			int x = z/3; // 9가 위치한 인덱스를 나중에 구하기위해
			int y = z%3; // 9가 위치한 인덱스를 나중에 구하기위해
			for(int k=0;k<4;k++) {
				int nx = x+dx[k]; // 네방향으로 이동하기 위해서
				int ny = y+dy[k]; // 네 방향으로 이동하기 위해서
				if(nx>=0 && nx<n && ny>=0 && ny<n) { //범위를 벗어나지 않도록 하기 위해서
					StringBuilder next = new StringBuilder(now);
					// 밑에는 9가 위치한 곳과 다른 곳의 위치를 교환하는 코드
					char temp = next.charAt(x*3+y);
					next.setCharAt(x*3+y, next.charAt(nx*3+ny));
					next.setCharAt(nx*3+ny, temp);
					
					int number = Integer.parseInt(next.toString());
					// map이 number를 포함하지 않으면 그 number의 상태를 1증가시킨다. 
					// 그리고 큐에 추가한다. 
		
					if(!map.containsKey(number)) {
						map.put(number, map.get(now_num)+1);
						q.add(number);
					}
				}
			}
			
		}
		if(map.containsKey(123456789)) {
			System.out.println(map.get(123456789));
		}else {
			System.out.println(-1);
		}
		
	}

}