[BOJ 1525] 퍼즐 (Java)

BOJ 1525 퍼즐

문제풀이

이 문제는 퍼즐을 맞추는 최소 시간을 알아내는 문제다. 2차원의 표 그리고 최소 시간을 보는 순간 딱 BFS라는 느낌이 왔다. 하지만 여러가지 문제점이 바로 떠올랐는데

• 현재 퍼즐이 맞춰진 상태인지 어떻게 체크할 것인가? 매번 2차원 배열을 확인하는 것은 큰 오버헤드가 발생할 것이다.
• 방문체크를 어떻게 하지? 단순히 빈칸의 위치만 가지고 체크를 할 수 없다. 같은 위치에 빈칸이 있더라도 다른 숫자의 상태가 다를 수 있기 때문이다.

결국 풀지 못하고 검색한 결과 정말 멋진 아이디어를 얻었다.

• 2차원 map을 1차원으로 나타내기
  - 현재 퍼즐의 상태가 String 또는 Integer로 나타나기 때문에 상태 체크가 굉장히 손쉽고 빠르게 가능하다.

  • 2차원 좌표와 1차원 좌표 사이의 변환

    			// 1차원 => 2차원
    			int nine = cur.indexOf('9');
    			int r = nine / 3;
    			int c = nine % 3;
    
    			// 2차원 => 1차원
    			int nine = 3 * r + c;

• HashMap을 활용한 방문 체크
  - 퍼즐의 전체 상태(1차원)를 key값으로 사용하면 정확하게 방문 체크할 수 있다.

나머지는 일반적인 BFS와 동일하게 진행하면 된다.

구현코드

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

public class Main {
	
	static HashMap<Integer, Integer> map;
	static Queue<Integer> q;
	static int[][] dir = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = null;
		
		// 2차원 퍼즐을 1차원으로 바꿔준다. 
		int start = 0;
		for(int i = 0 ; i < 3 ; ++i) {
			st = new StringTokenizer(br.readLine());
			for(int j = 0 ; j < 3 ; ++j) {
				int temp = stoi(st.nextToken());
				// 0일 때 9로 바꿔준다. 
				if(temp == 0) temp = 9;
				start = (start * 10) + temp;
			}
		}
		
		q = new LinkedList<>();
		map = new HashMap<>();

		q.offer(start);
		map.put(start, 0);
		
		System.out.println(bfs());
		
	}
	
	private static int bfs() {
		while(!q.isEmpty()) {
			// 큐에서 꺼낸 퍼즐의 상태를 문자열로 바꿔 9의 위치를 찾는다.
			int cur_int = q.poll();
			String cur = String.valueOf(cur_int);
			
			// 퍼즐이 맞춰진 상태일 경우 맵에서 시간을 꺼내고 리턴한다. 
			if(cur.equals("123456789")) {
				return map.get(cur_int);
			}
			
			int nine = cur.indexOf('9');
			// 현재 9의 좌표를 알아낸다. 
			// 몫 연산은 행, 나머지 연산은 열을 나타낸다.  
			int r = nine / 3;
			int c = nine % 3;
			
			for(int i = 0 ; i < 4 ; ++i) {
				int nr = r + dir[i][0];
				int nc = c + dir[i][1];
				if(nr >= 3 || nr < 0 || nc >= 3 || nc < 0) continue;
				
				StringBuilder next_str = new StringBuilder(cur);
				// r * 3 + c 는 좌표의 1차원 배열에서의 위치다.
				// 이전 9의 위치와 다음 위치의 숫자를 바꾼다. 
				char temp = next_str.charAt(nr * 3 + nc);
				next_str.setCharAt(nr * 3 + nc, '9');
				next_str.setCharAt(nine, temp);
				
				int next = stoi(next_str.toString());
				
				// 맵에 없는(나온적 없는 퍼즐의 상태) 경우에는 맵에 추가한다. 
				if(!map.containsKey(next)){
					map.put(next, map.get(cur_int) + 1);
					q.offer(next);
				}
			}
		}
		return -1;
	}
	
	private static int stoi(String s) {
		return Integer.parseInt(s);
	}
}