[백준 1525] 퍼즐- Java

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

1525번: 퍼즐

 

 

풀이

BFS를 사용한 완전탐색 방법으로 구현하였다.

현재의 퍼즐모양, 빈 칸의 위치, 이동 횟수를 저장하기 위해 Info 클래스를 만들었다.

 

탐색을 하다가 이전에 나왔던 퍼즐모양은 다시 만들 필요가 없기 때문에 방문 체크를 해야한다.

방문 체크를 위해 Map 자료구조를 사용했고 key값으로는 퍼즐을 Integer로 바꾼 것을 사용했다.

 

1	0	3
4	2	5
7	8	6

-> 687524301 = 1 * 10^0 + 0 * 10^1 + 3 * 10^2 + 4 * 10^3 + 2 * 10^4 + ... + 6 * 10^8

 

bfs는 다음과 같이 동작한다.

1. 0과 바꿀수 있는 위치 구하기

2. 바꾼 뒤 퍼즐 모양 구하기

3. 정리된 퍼즐 모양이면 현재 이동 횟수 + 1 반환

4. 방문체크 후 큐에 삽입.

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

public class 퍼즐 {
	static int[][] puzzle;
	static Map<Integer, Boolean> visit;
	static int[] start;
	static int[] dr = { -1, 0, 1, 0 };
	static int[] dc = { 0, 1, 0, -1 };

	static class Info {
		int[][] puzzle;
		int[] location0;
		int count;

		public Info(int[][] puzzle, int[] location0, int count) {
			super();
			this.puzzle = puzzle;
			this.location0 = location0;
			this.count = count;
		}

	}

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		puzzle = new int[3][3];
		visit = new HashMap<>();
		for (int i = 0; i < 3; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			for (int j = 0; j < 3; j++) {
				puzzle[i][j] = Integer.parseInt(st.nextToken());
				if (puzzle[i][j] == 0)
					start = new int[] { i, j };
			}
		}
		// 이미 정리된 퍼즐이면 0 출력
		if(toInt(puzzle) == 87654321) {
			System.out.println(0);
			return;
		}
		System.out.println(bfs());

	}

	private static int bfs() {
		Queue<Info> q = new LinkedList<>();
		q.offer(new Info(puzzle, start, 0));
		visit.put(toInt(puzzle), true);

		while (!q.isEmpty()) {
			Info current = q.poll();
			for (int d = 0; d < 4; d++) {
				int r = current.location0[0];
				int c = current.location0[1];
				int nr = r + dr[d];
				int nc = c + dc[d];
				if (nr >= 0 && nr < 3 && nc >= 0 && nc < 3) {
					int[][] newPuzzle = swap(current.puzzle, r, c, nr, nc);
					int key = toInt(newPuzzle);
					if(key == 87654321)
						return current.count + 1;
					if(!visit.containsKey(key)) {
						visit.put(key, true);
						q.offer(new Info(newPuzzle, new int[] {nr, nc}, current.count + 1));
					}
				}
			}
		}
		return -1;
	}
	
	// 퍼즐 위치 바꾸기
	private static int[][] swap(int[][] puzzle, int r, int c, int nr, int nc) {
		int[][] newPuzzle = new int[3][3];
		for(int i = 0; i < 3; i++) {
			for(int j = 0; j < 3; j++) {
				newPuzzle[i][j] = puzzle[i][j];
			}
		}
		int tmp = newPuzzle[r][c];
		newPuzzle[r][c] = newPuzzle[nr][nc];
		newPuzzle[nr][nc] = tmp;
		return newPuzzle;
	}
	
	// puzzle -> key값으로 변환
	private static int toInt(int[][] puzzle) {
		int result = 0;
		for (int i = 0; i < 3; i++) {
			for (int j = 0; j < 3; j++) {
				int idx = i * 3 + j;
				result += Math.pow(10, idx) * puzzle[i][j];
			}
		}
		return result;
	}

}