[백준] 1525번 - 퍼즐 (Java)

문제

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

1525번: 퍼즐

 

입력

 

출력

---

알고리즘

너비 우선 탐색 (BFS), 해시 맵 (Hashmap)

 

초기 게임판에서 아래와 같은 정렬된 상태로 만들 수 있는가?를 확인할 것이다. 일단 움직일 수 있는 최소 횟수를 물었으므로, 최단 경로를 물어보고 있는 것이다. 따라서 이 문제는 DFS로 풀 수 없다. 반드시 BFS로 풀어야한다.

 

그럼 단순하게 생각해본다면, 그냥 현재 게임판 상태 전체를 큐에 같이 넣고 돌리면 되지 않는가?라고 생각할 수 있다. 그런데, 큐에 이 이차원 배열을 통째로 넣고 돌리면 메모리 초과가 난다. 해당 문제는 메모리 제한이 32MB로 매우 작기 때문이다. 따라서, 다른 방법을 생각해야된다.

 

어차피 게임판의 크기는 정해져있으니, 현재 게임판의 상태를 하나의 스트링으로 나타내면 되지 않겠는가? 예를들어, 최종 정렬된 게임판의 상태는 위에서부터 쫘르륵 읽어서 (빈칸을 0이라고 가정함) "123456780"이라고 표현할 수 있다. 또다른 예시를 들어 보겠다.

위와 같은 상태는 "123450786"이라고 정의해서 저장하면 된다. 이러면 굳이 배열을 통째로 저장하지 않아도 되기 때문에 메모리가 아주 크게 절약될 것이다.

 

BFS를 돌릴때는 어떤걸 움직인다고 생각해줘야할까? 숫자 퍼즐 하나하나를 따져가면서 움직이는 것은 8종류의 숫자퍼즐을 4방향씩 체크해줘야되니 한번 반복에 32번을 움직여줘야 되므로 말도 안된다. 따라서, 반대로 빈칸을 움직인다고 생각하면 4방향만 체크해주면 되므로 훨씬 효율적이게 된다. 

 

그렇다면, 방문처리는 어떻게 해줘야될까? BFS를 돌리다가 또다시 똑같은 패턴이 나오면 전에 했던 행동을 계속 반복하고 무한 루프에 걸릴 것이다. 따라서, 방문처리를 해줘야한다. 만들어질 수 있는 경우의 수가 9!이니깐 362880개의 방문 배열을 만든다? 이건 안좋은 방법이다. 기껏 메모리 절약하려고 애썼는데 굳이 메모리를 많이 잡아먹는 방법을 이용할 필요가 없다. 그래서 사용할 것이 HashMap이다. 위에서 정의한 스트링의 현재 배열 상태를 키값으로 하고 value 값을 그 모양을 만들기 위한 최소 이동 횟수라고 정의하면 된다. 예시를 하나 들어보겠다.

 

1 0 3
4 2 5
7 8 6

위와 같은 입력이 들어왔다. 일단 초기 상태는 움직이는 횟수가 있을리가 없으므로 Hasmap에는 키값 "103425786", value 값 0이 들어가서 {"103425786" : 0} 이렇게 저장될 것이다. 여기서 빈칸을 이동해서 

0 1 3
4 2 5
7 8 6

위와 같은 상태를 만들었다면? 1번 움직였기 때문에 {"013425786" : 1} 이렇게 저장될 것이다. 이런식으로 BFS를 돌리면서 저 키 값이 Hashmap 안에 존재하는지 체크하고, 존재하지 않으면 hashmap에 추가해주고 queue에 넣어주는 방식으로 돌리면 된다.

---

코드

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

public class Main {
    static int[] dirx = {1,-1,0,0};
    static int[] diry = {0,0,1,-1};
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        String init = "";
        for(int i = 0; i<3; i++){
            StringTokenizer st = new StringTokenizer(br.readLine());
            for(int j = 0; j<3; j++){
                init += st.nextToken();
            }
        }

        System.out.println(bfs(init));
    }

    public static int bfs(String start){
        Queue<String> queue = new LinkedList<>();
        //visited의 역할을 해줄 것임
        //현재 게임판의 상태 : 이동횟수로 들어갈 것임.
        HashMap<String, Integer> map = new HashMap<String, Integer>();
        //초기 상태에는 이동횟수가 0번이다.
        map.put(start, 0);
        queue.add(start);

        //최종 정리된 상태(키값)
        String answer = "123456780";

        while(!queue.isEmpty()){
            String pos = queue.poll();
            //숫자를 움직인다고 생각하지말고, 빈칸인 0을 움직인다고 생각하는거임
            int zero = pos.indexOf('0');
            int x = zero/3;
            int y = zero%3;
            
            //현재 상태가 최종 정리된 키값이랑 같다면, 그때 이동 횟수를 출력
            if(pos.equals(answer)) return map.get(pos);
            
            //0이 다음에 움직일 위치에 대해서 BFS
            for(int i = 0; i<4; i++){
                int nx = x + dirx[i];
                int ny = y + diry[i];

                if(nx<0 || ny<0 || nx>=3 || ny>=3) continue;

                int npos = nx*3 + ny;
                char tmp = pos.charAt(npos);
                
                //0이 갈 위치와 기존에 있던 숫자 조각의 위치를 바꿔줌
                String next = pos.replace(tmp, 't');
                next = next.replace('0', tmp);
                next = next.replace('t', '0');
                
                //만약 한번도 나오지 못한 조합이면 큐에 넣어줌
                if(!map.containsKey(next)){
                    queue.add(next);
                    map.put(next, map.get(pos)+1);
                }
            }
        }

        return -1;
    }
}