[백준] 1525번 퍼즐 (Java)

백준 1525 퍼즐

격자의 크기가 별로 크지 않아 전체 경우의 수는 9!(=362,880)이기 때문에, 완전 탐색임을 금방 알 수 있지만 구현하는 과정이 까다로웠다. 처음엔 DFS를 활용하여 구현했지만, StackOverflow 에러가 발생했다. BFS 탐색을 활용하여 문제를 해결했지만, 격자점의 형태를 이미 방문했는지 확인하는 방법에서 굉장히 고생했다. 처음엔 HashMap에 2차원의 int 배열을 전달했지만, 배열의 메모리 주소를 해쉬 맵에 저장하기 때문에, 요소를 비교하기에는 불편함이 있었다. 결국 HashMap의 Key는 String으로 value는 변화 횟수인 int를 활용하기로 했다.

1. 최솟값 탐색 & 깊이가 깊어질 수 있기 때문에 BFS 활용(StackOverflow error 방지)
2. 배열의 형태는 HashMap<String, Integer>을 활용하여 방문했는지 확인하고, 횟수도 확인
3. BFS이기 때문에 이미 방문했던 노드에 재방문 하는 것은 최솟값이 될 수 없음.
4. StringBuilder를 활용해 빈칸의 이동 구현

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

public class Main {
    static StringBuilder sb;
    // 중복 방지할 HashMap
    static HashMap <String, Integer> hm = new HashMap<>();

    // 왼쪽으로 이동
    static String moveLeft(String s, int idx){
        char tc = s.charAt(idx);
        sb = new StringBuilder(s);
        sb.setCharAt(idx, s.charAt(idx - 1));
        sb.setCharAt(idx - 1, tc);
        return sb.toString();
    }

    // 오른쪽으로 이동
    static String moveRight(String s, int idx) {
        char tc = s.charAt(idx);
        sb = new StringBuilder(s);
        sb.setCharAt(idx, s.charAt(idx + 1));
        sb.setCharAt(idx + 1, tc);
        return sb.toString();
    }

    // 위로 이동
    static String moveUp(String s, int idx){
        char tc = s.charAt(idx);
        sb = new StringBuilder(s);
        sb.setCharAt(idx, s.charAt(idx - 3));
        sb.setCharAt(idx - 3, tc);
        return sb.toString();
    }

    // 아래로 이동
    static String moveDown(String s, int idx){
        char tc = s.charAt(idx);
        sb = new StringBuilder(s);
        sb.setCharAt(idx, s.charAt(idx + 3));
        sb.setCharAt(idx + 3, tc);
        return sb.toString();
    }

    static void bfs(String input){
        Queue <String> q = new LinkedList<>();
        String tmp, changed;
        int idx, cost;
        q.add(input);
        hm.put(input, 0);
        while(!q.isEmpty()){
            tmp = q.poll();
            if(tmp.equals("123456780")){
                if(hm.containsKey(tmp)){
                    System.out.println(hm.get(tmp));
                    System.exit(0);
                }
            } else{
                idx = tmp.indexOf("0");
                cost = hm.get(tmp);

                // 빈칸이 왼쪽으로
                if(idx % 3 != 0){
                    changed = moveLeft(tmp, idx);
                    if(!hm.containsKey(changed)){
                        hm.put(changed, cost + 1);
                        q.add(changed);
                    }
                }

                // 빈칸이 오른쪽으로
                if(idx % 3 != 2){
                    changed = moveRight(tmp, idx);
                    if(!hm.containsKey(changed)){
                        hm.put(changed, cost + 1);
                        q.add(changed);
                    }
                }

                // 빈칸이 위쪽으로
                if(idx / 3 != 0){
                    changed = moveUp(tmp, idx);
                    if(!hm.containsKey(changed)){
                        hm.put(changed, cost + 1);
                        q.add(changed);
                    }
                }

                // 빈칸이 아래쪽으로
                if(idx / 3 != 2){
                    changed = moveDown(tmp, idx);
                    if(!hm.containsKey(changed)){
                        hm.put(changed, cost + 1);
                        q.add(changed);
                    }
                }
            }
        }
        // 예외처리
        System.out.println(-1);
    }



    public static void main(String[] args) {
        try {
            int zy = 0, zx = 0;
            String tmp;
            BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
            BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
            StringTokenizer st;
            sb= new StringBuilder();
            for(int i = 0; i < 3; i ++){
                st = new StringTokenizer(br.readLine());
                for(int j = 0; j < 3; j ++){
                    sb.append(Integer.parseInt(st.nextToken()));
                }
            }
            bfs(sb.toString());
        } catch (Exception e) {
            e.printStackTrace();
        }
    }
}