#백준_1525 퍼즐 - Java

# 유형 : 탐색

# 맨 처음엔 어떻게 접근해야 많이 고민했는데, 0 을 9로 바꾸고 배열을 스트링으로 길게 뽑아서 연결하여 스트링이 123456789를 만들때까지 탐색을 하면 된다. 간단하게 말하면 

첫 번째 예제로 나와있는 아래의 값을 193425786으로 바꾼다. 그리고 9를 기준으로 삼아 계속 움직이면서 123456789로 바꾸는 데 카운트를 체크하면 된다. map을 쓰면 더 편하다.

1 0 3 

4 2 5

7 8 6

 

 

 

package bj;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;
import java.util.Queue;
import java.util.StringTokenizer;

public class p1525 {
	static int arr[][];
	static int moveX[] = {0,1,0,-1};
	static int moveY[] = {-1,0,1,0};
	static Map<Integer, Integer> map = new HashMap<Integer, Integer>();
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		arr = new int[3][3];
		StringTokenizer st;
		int value = 0;
		for(int i=0; i<3; i++) {
			st = new StringTokenizer(br.readLine());
			for(int j=0; j<3; j++) {
				int val = Integer.parseInt(st.nextToken());
				if(val==0)
					val=9;
				
				value = value*10 + val;
				
				arr[i][j] = val;
			}
		}
		
		bfs(value);
		
		if(map.containsKey(123456789))
			System.out.println(map.get(123456789));
		else
			System.out.println(-1);
	}
	private static void bfs(int val) {
		Queue queue = new LinkedList<>();
		queue.add(val);
		map.put(val, 0);
		while(!queue.isEmpty()) {
			int tmp = queue.poll();
			String number = String.valueOf(tmp);
			int index = number.indexOf("9");
			
			int y = index/3;
			int x = index%3;
			
			for(int d=0; d<4; d++) {
				int newY = y + moveY[d];
				int newX = x + moveX[d];
				
				int nextIndex = newY*3 + newX;
				if(0<=newY && newY<3 && 0<=newX && newX<3) {
					StringBuilder sb = new StringBuilder(number);
					char tmpChar = sb.charAt(index);
					sb.setCharAt(index, sb.charAt(nextIndex));
					sb.setCharAt(nextIndex, tmpChar);
					
					int nextVal = Integer.parseInt(sb.toString());
					if(!map.containsKey(nextVal)) {
						map.put(nextVal, map.get(tmp)+1);
						queue.add(nextVal);
					}
				}
			}
		}
	}
}