[골드2, BFS] 백준 1525 - 퍼즐 (자바)

Think

1. 30분정도 고민했는데 방법이 생각이 안났다. 규칙성이 있지 않을까 하면서 BFS를 활용해서 구현하는 방법을 고민했지만… 안됐다
2. https://loosie.tistory.com/253 를 참고했다.
3. 0을 기준으로 BFS하면서 완전탐색을 하는 방식이었다.
4. 0이 상하좌우 움직일때의 모든 경우의 수를 탐색해야하는데, boolean[][] 배열로는 불가능? 비효율?적이기 때문에 HashMap을 사용하여 중복체크를 한다.
5. 또한, input을 2차원배열로 저장하지 않고, String으로 관리한다. 탐색할때는 나머지연산, 나누기 연산을 활용해서 위치를 관리한다.
6. 이렇게 새로운 풀이방식이 나때마다 어떻게 이런 생각을 할까 하면서 감탄하게 된다 ㅎ.ㅎ..

 

내 정답 코드

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

public class test {
    static String puzzle = "";
    static String correctPuzzle = "123456780";
    static StringBuilder newPuzzle;
    static Map<String, Integer> isVisitedMap = new HashMap<>();
    static int[] dr = new int[]{0, 0, 1, -1};
    static int[] dc = new int[]{1, -1, 0, 0};

    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;

    public static void main(String[] args) throws IOException {
        init();

        process();
    }

    private static void process() {

        Queue<String> q = new ArrayDeque<>();

        q.add(puzzle); 
        isVisitedMap.put(puzzle , 0);

        while(!q.isEmpty()){
            puzzle = q.poll();

            int zeroIndex = puzzle.indexOf("0");
            int zeroR = zeroIndex / 3;
            int zeroC = zeroIndex % 3;

            if(correctPuzzle.equals(puzzle)) {
                System.out.println(isVisitedMap.get(puzzle));
                return;
            }

            for (int i = 0; i < 4; i++) {
                int nextZeroR = zeroR + dr[i];
                int nextZeroC = zeroC + dc[i];

                if(nextZeroR < 0 || nextZeroC < 0 || nextZeroR >= 3 || nextZeroC >= 3)  continue;

                int nextZeroIndex = nextZeroR * 3 + nextZeroC;

                newPuzzle = new StringBuilder(puzzle);
                char tempChar = newPuzzle.charAt(nextZeroIndex);
                newPuzzle.setCharAt(nextZeroIndex, '0');
                newPuzzle.setCharAt(zeroR * 3 + zeroC, tempChar);

                if(!isVisitedMap.containsKey(newPuzzle.toString())){
                    q.add(newPuzzle.toString());
                    isVisitedMap.put(newPuzzle.toString(), isVisitedMap.get(puzzle) + 1);

                }
            }
        }

        System.out.println(-1);
    }

    private static void init() throws IOException {

        for (int i = 0; i < 3; i++) {
            puzzle += br.readLine().replaceAll(" ", "");
        }
    }
}