[Java] 백준 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

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

입력

세 줄에 걸쳐서 표에 채워져 있는 아홉 개의 수가 주어진다. 한 줄에 세 개의 수가 주어지며, 빈 칸은 0으로 나타낸다.

출력

첫째 줄에 최소의 이동 횟수를 출력한다. 이동이 불가능한 경우 -1을 출력한다.

예제 입력 1

1 0 3
4 2 5
7 8 6

예제 출력 1

3

예제 입력 2

3 6 0
8 1 2
7 4 5

예제 출력 2 

-1

 

 

소스코드

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 Main {

	private static BufferedReader br;
	private static StringTokenizer st;
	
	private static String map;
	private static String result="123456780";	// 정리된 상태
	private static Map<String, Integer> m=new HashMap<>();	// 키: 퍼즐의 상태, 값: 이동 횟수
	private static int []dx= {-1,1,0,0};
	private static int []dy= {0,0,-1,1};
	
	public static void main(String[] args) throws IOException {
		br=new BufferedReader(new InputStreamReader(System.in));
		map="";
		for(int r=0;r<3;r++) {	// 퍼즐의 상태를 문자열로 저장함
			st=new StringTokenizer(br.readLine());
			for(int c=0;c<3;c++) {
				map+=st.nextToken();
			}
		}
		m.put(map, 0);	// 시작 상태와 이동 횟수 0을 맵에 저장
		int ans=bfs(map);	// bfs를 통해 최소 이동으로 정리된 상태가 되는 횟수를 구함
		System.out.println(ans);
	}

	private static int bfs(String s) {
		Queue<String> queue=new LinkedList<>();
		queue.add(s);
		
		while(!queue.isEmpty()) {
			String q=queue.poll();	// 큐에 들어있는 문자열을 하나 빼냄
			int zero=q.indexOf('0');	// 문자열에서 0의 위치를 찾음
			int r=zero%3;	// 좌표로 나타내었을 때 0의 행
			int c=zero/3;	// 좌표로 나타내었을 때 0의 열
			
			if(q.equals(result)) return m.get(q);	// 현재 문자열이 정리된 상태와 일치하면 이동 횟수 리턴
			for(int d=0;d<4;d++) {	// 사방탐색
				int nx=r+dx[d];
				int ny=c+dy[d];
				
				if(isIn(nx, ny)) {	// 범위 내에 있을 때
					int pos=nx+ny*3;	// 문자열에서의 위치
					char ch=q.charAt(pos);	// 현재 문자
					String tmp=q.replace(ch, 'a');	// 0과 현재 문자를 교환
					tmp=tmp.replace('0', ch);
					tmp=tmp.replace('a', '0');
					if(!m.containsKey(tmp)) {	// 맵에 존재하지 않는 문자열인 경우 맵에 새롭게 저장
						m.put(tmp, m.get(q)+1);
						queue.add(tmp);
					}
				}
			}
		}
		return -1;	// 모든 경우를 탐색하여 정리된 상태를 찾지 못한 경우 -1을 리턴
	}
	
	
	private static boolean isIn(int r, int c) {
		return r>=0 && r<3 && c>=0 && c<3;
	}
	
}

처음에는 copyMap을 통해 퍼즐의 상태를 2차원 배열로 복사하여 dfs로 해결하려고 했으나, 2차원 배열을 관리해주기 너무 어렵고, dfs도 아니라는 것을 알게 되었습니다.

우선 '최소 이동'을 찾아야 하므로 bfs를 이용해주었는데, 퍼즐의 상태를 효율적으로 관리해주기 위해 문자열과 맵 구조를 이용했습니다. 끝내 이런 방법을 생각해내지 못해서 아래 블로그를 참고하여 해결했으니 참고하시면 좋을 것 같습니다.

 

https://loosie.tistory.com/253

[BOJ] 백준 1525번 퍼즐 (Java)