백준 1525번: 퍼즐 (Java)

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

1525번: 퍼즐

 

 

 

 

 

 

 

---

 

풀이

처음 보면 꽤 막막합니다. 케이스를 잘 나누어 각 경우마다 최적의 움직임을 수행하면 될까? 일단 케이스를 분류하는거조차 모르겠고, 각 상황별 최적의 움직임이 뭔지도 모르겠네요. 이 방법은 아닌 듯 합니다.

한 단계의 움직임을 분석해보니까, 0을 (가능한 방향의) 사방의 숫자랑 바꾸는 것이고, 이는 사방 탐색으로 구현할 수 있어 보입니다. 거기에다가 특정 상태에 가장 먼저 도착...? => BFS로 될 겁니다.

그러면, 상태 공간을 저장할 배열을 만들어야 할 겁니다. 가장 간단한 방법은 각 칸의 크기가 9인 9차원(!) 배열을 만들어, 각각의 칸의 숫자랑 대응시킬 수 있을 겁니다. 다만 int 9^9개 배열을 선언하면 문제의 메모리 제한에 걸릴 겁니다.

즉, 상태를 조금 더 간단하게 나타내어 32MB 이내로 모든 상태를 저장할 수 있도록 해야합니다. 생각해보면 0~8사이의 수는 1칸에 딱 한 번만 들어가야 하기에, 경우의 수는 9! = 362880가지가 될 거고, 이 경우만 저장한다면 메모리 초과가 발생하지 않을 겁니다.

방법이야 다양하게 있겠지만, 저는 좌측 상단부터 우측 하단까지의 숫자를 쭉 적은 방법으로 상태를 저장했습니다. 가령, '예제 입력 1'의 상태를 103425786이라는 정수로 대응시키는 거죠. 이를 Map에 <상태, 이동 횟수>를 저장하여 각 상태별로 최적의 이동회수를 저장했습니다.

참고로, 상태를 "103425787"과 같은 String으로 저장할 수도 있으나, 1)String 관련 내장함수를 잘 몰라서, 2)각종 String manipulation(concat, replace 등...)이 죄다 O(N) 시간복잡도라 사용하지 않았습니다. 근데 다른 분들 풀이 보면 String으로 상태를 저장해도 (살짝 느리지만) 시간 내에 잘 되더라고요. 

이후 0을 움직여주면 됩니다. 처리가 살짝 지저분한데, 어려운 건 아니니 적당히 해줍시다.

 

 

코드

import java.io.*;
import java.util.*;
 
public class Main {
    static int[] dr = { -1, 1, 0, 0 };
    static int[] dc = { 0, 0, -1, 1 };
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int[][] locToidx = new int[][] {{2, 2}, {2, 1}, {2, 0}, {1, 2}, {1, 1}, {1, 0}, {0, 2}, {0, 1}, {0, 0}};
        int[][] idxToloc = new int[][] {{8, 7, 6}, {5, 4, 3}, {2, 1, 0}};
        int first = 0;
        int zero = 0;
        for (int i = 0; i < 3; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int j = 0; j < 3; j++) {
                first *= 10;
                int temp = Integer.parseInt(st.nextToken());
                first += temp;
                if (temp == 0) {
                    zero = idxToloc[i][j];
                }
            }
        }
        HashMap<Integer, Integer> memo = new HashMap<>();
        memo.put(first, 0);
        Queue<Info> queue = new ArrayDeque<>();
        queue.offer(new Info(zero, first));
        while (!queue.isEmpty()) {
            Info cur = queue.poll();
            int[] idx = locToidx[cur.zeroLoc];
            int r = idx[0], c = idx[1];
            for (int i = 0; i < 4; i++) {
                int nr = r + dr[i], nc = c + dc[i];
                if (nr < 0 || nr >= 3 || nc < 0 || nc >= 3) continue;
                int nxtzeroLoc = idxToloc[nr][nc];
                int num = cur.status;
                for (int j = 0; j < nxtzeroLoc; j++) {
                    num /= 10;
                }
                num %= 10;
                int nxtStatus = cur.status + num * (int) Math.pow(10, cur.zeroLoc) - num * (int) Math.pow(10, nxtzeroLoc);
                if (memo.containsKey(nxtStatus)) continue;
                memo.put(nxtStatus, memo.get(cur.status) + 1);
                queue.offer(new Info(nxtzeroLoc, nxtStatus));
            }
        }
        if (!memo.containsKey(123456780)) System.out.println(-1);
        else System.out.println(memo.get(123456780));
    }
    
    static class Info {
        int zeroLoc;
        int status;
        
        public Info(int zeroLoc, int status) {
            this.zeroLoc = zeroLoc;
            this.status = status;
        }
    }
}