89. 퍼즐 (백준 1525) [JAVA]

 

문제

문제 링크 : https://www.acmicpc.net/problem/1525

1525번: 퍼즐

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
1초	32MB	10927	4626	2790	40.629%

문제

3×3 표에 다음과 같이 수가 채워져 있다. 오른쪽 아래 가장 끝 칸은 비어 있는 칸이다.

1	2	3
4	5	6
7	8

어떤 수와 인접해 있는 네 개의 칸 중에 하나가 비어 있으면, 수를 그 칸으로 이동시킬 수가 있다. 물론 표 바깥으로 나가는 경우는 불가능하다. 우리의 목표는 초기 상태가 주어졌을 때, 최소의 이동으로 위와 같은 정리된 상태를 만드는 것이다.

입력

세 줄에 걸쳐서 표에 채워져 있는 아홉 개의 수가 주어진다. 한 줄에 세 개의 수가 주어지며, 빈 칸은 0으로 나타낸다.

출력

첫째 줄에 최소의 이동 횟수를 출력한다. 이동이 불가능한 경우 -1을 출력한다.

 

문제

처음에는 3X3 퍼즐이 풀 수 있는 공식이 있는가 생각하면서, 불가능한 경우 (치환 퍼즐)의 조건을 생각하려 했으나 너무 어려웠다.

그래서 결국 완전탐색을 사용해야 한다고 생각했고, 퍼즐 이동의 최단거리이기 때문에, BFS를 사용하여 문제를 해결해야 한다고 생각했다.

각각의 빈 공간에서 -> 교체할 수 있는 블록의 위치를 큐에 담아가면서 모든 이동가능한 경우를 고려하는 방법이다.

조건에 따라 JAVA는 256MB까지지만, 여하튼 32MB의 악독한 메모리 조건에 겁을 먹어서 하드코딩을 좀 박아버렸다. 문제가 3*3퍼즐로 고정되어 있기 때문에, 각각의 좌표가 0일때(빈 공간) 이동할 수 있는 좌표를 0~8의 일자형 배열에서의 인덱스라 생각하고 저장해두었다 (moveMap)

이때 각각 경우의 "상태"를 어떻게 저장할 까 고민하다, 그냥 문자열로 저장하기로 하였다.

3*3퍼즐로 고정되어있기 때문에 정답은 "123456780"이고, 각각의 퍼즐 상태 역시 이와 같이 문자열로 저장하고, 블록의 교체는 Stringbuilder의 replace와 charAt을 사용하여 구현하였다.

그냥 String은 replace도 없고, 내부적으로 매번 새 문자열을 만들기 때문에 메모리를 많이 먹을 거것 같았다.

그리고 중복 여부를 체크하지 않으면, 퍼즐이 무한루프를 돌 수 있는데, 해당 상태가 중복된 상태임을 표현하기 위해 HashMap을 사용하였다.

3*3의 배열이 가능한 상태 (되는경우, 안되는 경우 포함) -> 9! = 362880 가지 * 4byte = 13MB인데다, 실제로 퍼즐은 저 모든 상태이지도 않기 때문에 충분히 여유가 있을 것이라 생각했다.

그렇게 정답 문자열이 나올 때 까지 BFS를 진행하고, 가능한 모든 상태를 만족시켜 더 이상 움직일 수 없으면 -1을 출력하도록 하였다.

 

코드

import java.io.*;
import java.nio.channels.FileChannel.MapMode;
import java.util.*;

public class Main {

    static int[][] moveMap = {{1,3}, {0,2,4}, {1,5},
                            {0,4,6}, {1,3,5,7}, {2,4,8},
                            {3,7}, {6,4,8}, {7,5}};

    //가능한 상태 -> 9! = 362880 가지 * 4byte = 13MB
    static HashMap<String, Integer> cacheMap = new HashMap<>();
    static StringBuilder sb = new StringBuilder();
    //정리된 상태 -> 123 / 456 / 780
    // 0 -> 1, 3
    // 1 -> 0, 2, 4
    // 2 -> 1, 5
    // 3 -> 0, 4, 6
    // 4 -> 1, 3, 5, 7
    // 5 -> 2, 4, 8
    // 6 -> 3, 7
    // 7 -> 6, 4, 8
    // 8 -> 7, 5


    public static void main(String[] args) throws IOException{
        BufferedReader br = new java.io.BufferedReader(new InputStreamReader(System.in));
        String map = "";

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

        Queue<String> q = new LinkedList<>();
        q.add(map);

        int round = 0;
        int size = 0;

        while(!q.isEmpty()) {
            size = q.size();

            for(int i=0; i<size; i++) {

                String cur = q.poll();
                int zeroPt = cur.indexOf('0');

                //종료
                if(ansCheck(cur)) {
                    System.out.println(round);
                    return;
                }

                for(int j=0; j < moveMap[zeroPt].length; j++) {
                    int movePoint = moveMap[zeroPt][j];
                    String next = swap(cur, movePoint,zeroPt);
                    if(mapCheck(next)) {
                        q.add(next);
                    }
                }
            }
            round++;
        }
        System.out.println(-1);


    }

    public static boolean mapCheck(String s) {
        if(cacheMap.containsKey(s)){
            return false;
        }
        else {
            cacheMap.put(s,1);
            return true;
        }
    }

    public static boolean ansCheck(String s) {
        if(s.equals("123456780")) {
            return true;
        }
        return false;
    }

    public static String swap(String s, int a, int b) {
        //초기화 후 시작
        sb.setLength(0);
        //a의 문자를 b의 자리로 , b에는 0 
        sb.append(s);
        sb.setCharAt(b, s.charAt(a));
        sb.setCharAt(a, '0');
        return sb.toString();
    }
}

 

결과