[BaekJoon] 1525 퍼즐 (Java)

1.  문제 링크

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

2.  문제

요약

• 3 x 3 표에 수가 채워져 있습니다.
• 어떤 수와 인접해 있는 네 칸 중에 하나가 비어 있다면, 수를 그 칸으로 이동시킬 수 있습니다.
• 초기 상태가 주어졌을 때, 아래와 같은 정리된 상태를 만들기 위해 이동해야 하는 최소의 이동횟수를 구하는 문제입니다.

  1	2	3
  4	5	6
  7	8

• 입력: 세 개의 줄에 걸쳐서 표에 채워져 있는 아홉 개의 수가 주어집니다. 한 줄에 세 개의 수가 주어져며, 빈 칸은 0으로 나타냅니다.
• 출력: 첫 번째 줄에 최소의 이동 횟수를 출력합니다. 이동이 불가능한 경우 -1을 출력합니다.

3.  소스코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    static final int SIZE = 3;
    static final String RESULT="123456780";
    static String info;
    static Map<String, Integer> map = new HashMap<>();
    static int[] dx = {-1, 0, 1, 0}, dy = {0, -1, 0, 1};
    static int answer;

    static void input() {
        Reader scanner = new Reader();
        info = "";
        map = new HashMap<>();

        for(int row = 0; row < SIZE; row++) {
            for(int col = 0; col < SIZE; col++)
                info += scanner.next();
        }

        map.put(info, 0);
    }

    static void solution() {
        answer = Integer.MAX_VALUE;

        bfs(info);

        System.out.println(answer == Integer.MAX_VALUE ? -1 : answer);
    }

    static void bfs(String info) {
        Queue<String> queue = new LinkedList<>();
        queue.offer(info);

        while(!queue.isEmpty()) {
            String cur = queue.poll();
            int moveNum = map.get(cur);
            int emptyIdx = cur.indexOf('0');

            if(cur.equals(RESULT)) {
                answer = moveNum;
                return;
            }

            for(int dir = 0; dir < 4; dir++) {
                int cx = emptyIdx / SIZE + dx[dir], cy = emptyIdx % SIZE + dy[dir];

                if(isInMap(cx, cy)) {
                    int idx = cx * SIZE + cy;
                    char num = cur.charAt(idx);

                    String next = cur.replace(num, '9');
                    next = next.replace('0', num);
                    next = next.replace('9', '0');

                    if(!map.containsKey(next)) {
                        queue.offer(next);
                        map.put(next, moveNum + 1);
                    }
                }
            }
        }
    }

    static boolean isInMap(int x, int y) {
        if(x >= 0 && x < SIZE && y >= 0 && y < SIZE) return true;
        return false;
    }

    public static void main(String[] args) {
        input();
        solution();
    }

    static class Reader {
        BufferedReader br;
        StringTokenizer st;

        public Reader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        String next() {
            while(st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }
    }
}