백준 1525 (퍼즐)

문제

---

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

가장 윗 상태에서 세 번의 이동을 통해 정리된 상태를 만들 수 있다. 이와 같이 최소 이동 횟수를 구하는 프로그램을 작성하시오.

 

 

 

풀이

---

 

문제를 보면 BFS(너비 우선 탐색)로 풀어야 한다는 생각이 들지 않는다.

이문제를 풀기 위해서는 여러가기 조건과 스킬이 필요하다. 기존의 그래프 문제들과는 다르다.

 

2차 배열로 BFS 를 풀기는 어렵기 때문에 

1차 배열로 풀어주어야한다.

 

여기서 123456780 의 순서로 되어있는지 반복문을 통해 검사 할경우 시간복잡도가 커지기 때문에

HashMap 을 통해 123456780의 수가 속해있는지 확인하면 편하다.

 

하지만 여기서 0으로 계속 할 경우 012345678 의 경우 처럼 0이 제일 앞에 오는 경우 이를 수로 바꿔주면 12345678이 되기때문에 0으로는 계속 할  수가 없다.

 

이 경우를 막기위해 0 을 9로 치환한다.

 

dx = { 0, 0, 1, -1}

dy = { 1, -1, 0, 0} 이 두개의 배열을 이용하여 0위치의 상하 좌우를 분석한다.

 

123456789 형태가 됐을때 딱 모든 반복문이 종료 되는 것이 아닌

빈칸을 움직이다가 123456789의 형태가 되는지를 판단하고 그때의 이동 횟수를 뽑아내는 문제가 되겠다.

 

<2차 배열 형태로 주어진 숫자를 하나의 수로 변형하는 코드>

int start = 0;
for(int i = 0 ; i < 3 ; i++) {
	StringTokenizer st = new StringTokenizer(bufferedReader.readLine());
	for(int j = 0 ; j < 3 ; j++) {
		int num = Integer.parseInt(st.nextToken());
		
		if( num == 0) 
			num = 9;
		 
		start = start * 10 + num;
	}
}

수가 0 이라면 9로 변형을 시켜주고,

 

1 0 3

4 2 5

7 8 6  의 경우라면 193425786 의 수로 변형하여 저장하는 코드가 되겠다.

 

 

<BFS 코드>

while(!queue.isEmpty()) {
			
	int num = queue.poll();
	String number = String.valueOf(num);
	int nine = number.indexOf("9");
	int x = nine / 3;
	int y = nine % 3;

	for(int i = 0 ; i < 4 ; i++) {
		int nx = x + dx[i];
		int ny = y + dy[i];
				
		if(nx >= 0  && ny >= 0 && nx < 3 && ny <3) {
			int move = nx * 3 + ny;
				
			StringBuilder next = new StringBuilder(number);
					
			char temp = next.charAt(move);
			next.setCharAt(move, '9');
			next.setCharAt(nine, temp);
					
			int nextNumber = Integer.parseInt(next.toString());
					
			if(!hm.containsKey(nextNumber)) {
				hm.put(nextNumber, hm.get(num) + 1);
				queue.add(nextNumber);
			}
		}
	}		
}

여기서 queue 에는 빈칸의 상하좌우로 수를 옮겨준 이후의 수를 넣어준다.

 

HashMap을 이용해 수를 키(Key)로 저장하고 그때의 옮겨준 횟수를 값(Value)으로 넣어준다.

 

<전체코드>

import java.io.*;
import java.util.*;

public class Main {	
	static StringBuilder sb = new StringBuilder();
	static int[] dx = {0, 0, -1, 1};
	static int[] dy = {-1, 1, 0, 0};
	
	public static void main(String[] args) throws IOException{
		
		BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));

		int start = 0;
		for(int i = 0 ; i < 3 ; i++) {
			StringTokenizer st = new StringTokenizer(bufferedReader.readLine());
			for(int j = 0 ; j < 3 ; j++) {
				int num = Integer.parseInt(st.nextToken());
				
				if( num == 0) 
					num = 9;
				 
				start = start * 10 + num;
			}
		}
		
		Queue<Integer> queue = new LinkedList<Integer>();
		HashMap<Integer, Integer> hm = new HashMap<>();
		
		hm.put(start, 0);
		queue.add(start);
		
		while(!queue.isEmpty()) {
			
			int num = queue.poll();
			String number = String.valueOf(num);
			int nine = number.indexOf("9");
			int x = nine / 3;
			int y = nine % 3;

			for(int i = 0 ; i < 4 ; i++) {
				int nx = x + dx[i];
				int ny = y + dy[i];
				
				if(nx >= 0  && ny >= 0 && nx < 3 && ny <3) {
					int move = nx * 3 + ny;
					
					StringBuilder next = new StringBuilder(number);
					
					char temp = next.charAt(move);
					next.setCharAt(move, '9');
					next.setCharAt(nine, temp);
					
					int nextNumber = Integer.parseInt(next.toString());
					
					if(!hm.containsKey(nextNumber)) {
						hm.put(nextNumber, hm.get(num) + 1);
						queue.add(nextNumber);
					}
				}
			}		
		}
		if(hm.containsKey(123456789)) {
			System.out.println(hm.get(123456789));
		}
		else {
			System.out.println(-1);
		}
		
		System.out.println();
	}
	
}