[백준_1525번] 퍼즐

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

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으로 나타낸다.

 

[코드]

import java.util.*;

public class BaekJoon_1525 {
	/*
	 * key 값에는 퍼즐을 정수로 나타낸 값이 저장되며, 
	 * value 값에는 해당 정수를 만들기까지 퍼즐의 이동 횟수가 저장된다. 
	 */
	static Map<Integer,Integer> map=new HashMap<>();
	static int[] dx= {-1,0,1,0};
	static int[] dy= {0,-1,0,1};
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc=new Scanner(System.in);
		
		/*
		 * 2차원의 배열로 주어지는 퍼즐을 일렬로 주어지는 숫자처럼 생각하는 것이 편하다.
		 * 따라서 아래 과정을 통해 9자리의 정수로 나타낸다.
		 */
		int start=0;
		for(int i=0;i<3;i++) {
			for(int j=0;j<3;j++) {
				int num=sc.nextInt();
				if(num==0)
					num=9;
				
				start=(start*10)+num;
			}
		}
		
		map.put(start,0); 
		bfs(start);
		
		// 제대로 맞춰진 123456789가 저장되어 있다면 이동 횟수 출력
		if(map.containsKey(123456789))
			System.out.println(map.get(123456789));
		// 퍼즐이 맞춰지지 않았다면 -1 출력
		else
			System.out.println(-1);
	}
	
	/*
	 * 퍼즐의 0을 9로 바꿨기 때문에 9자리의 정수 중 9의 위치를 찾고,
	 * 9의 위치를 상,하,좌,우 이동시킨다. 
	 */
	static void bfs(int start) {
		Queue<Integer> q=new LinkedList<>();
		q.offer(start);
		
		while(!q.isEmpty()) {
			int now=q.poll();
			String now_str=String.valueOf(now); // 정수를 String으로 변환
			int nine_index=now_str.indexOf("9"); // 9의 인덱스를 찾는다
			
			int x=nine_index/3; // 9가 2차원 배열에서 몇 번째 행에 위치하는지 계산
			int y=nine_index%3; // 9가 2차원 배열에서 몇 번에 열에 위치하는지 계산
			
			// 상,하,좌,우 이동
			for(int i=0;i<4;i++) {
				int nx=x+dx[i]; 
				int ny=y+dy[i];
				int move=nx*3+ny; // 2차원 배열에서 이동한 인덱스를 1차원 배열의 인덱스로 변경
				
				// 배열의 범위를 벗어난 경우 넘어간다. 
				if(nx<0||ny<0||nx>=3||ny>=3)
					continue;
				
				// 이동할 수 있다면 이동할 인덱스에 있는 숫자와 9를 swap
				StringBuilder next_str=new StringBuilder(now_str);
				char temp=next_str.charAt(move);
				next_str.setCharAt(move,'9');
				next_str.setCharAt(nine_index, temp);
				
				int next_num=Integer.parseInt(next_str.toString());
				// 해당 경우가 이전에 나온적 없는 퍼즐 배치라면 이동횟수를 1 증가시킨 후 저장
				if(!map.containsKey(next_num)) {
					map.put(next_num,map.get(now)+1);
					q.offer(next_num);
				}
			}
		}
	}
}

 

[고찰]

 이번 문제의 핵심은 2차원의 형태로 주어지는 퍼즐을 1차원의 형태로 변경시키는 것이다. 이때 첫 번째에 빈 칸이 주어질 경우도 있기 때문에 하나의 정수로 구하기 위해서는 0을 9로 변경시키는 것이 편리하다. 또한 Map 자료구조를 사용하여 만들어진 정수와, 해당 정수를 만들기 위해 이동한 횟수를 동시에 저장하도록 해야한다. 

 이후 BFS 알고리즘을 사용하여 빈 공간을 옮겨주면 된다. 퍼즐의 빈 공간인 9의 위치를 찾아내고, 상, 하, 좌, 우로 이동시킨다. 이때 1차원의 인덱스를 2차원의 인덱스로 변경시킨 후 9의 위치를 옮겨 해당 위치로 이동할 수 있는지 체크해야 한다. 이동할 수 있다면 다시 2차원의 인덱스를 1차원으로 변경시켜 퍼즐을 이동시킨다. 

 이렇게 만들어진 정수가 이전에 나온적이 없던 퍼즐 배치라면 이동 횟수를 1 증가시킨 후 저장한다. 최종적으로 원하는 퍼즐의 배치인 123456789가 저장되어 있다면 value 값을 출력해주면 된다. 

 

 이번 문제는 아이디어를 떠올리는 것이 가장 중요한 문제였다. 스스로는 해결하지 못해 다른 사람의 포스팅을 보고 참고한 점이 아쉬웠다. 또한 자바 라이브러리가 제공하는 함수를 활용하면 더 효율적으로 풀 수 있는 문제였다.