[백준] 1525 퍼즐 java

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

public class Puzzle {
    static BufferedReader br;
    static StringTokenizer st;
    static final int[] dx = {-1, 1, 0, 0};
    static final int[] dy = {0, 0, -1, 1};
    static String input = "";
    static final String ans = "123456780";
    static HashMap<String, Integer> map = new HashMap<>();

    public static void main(String[] args) throws IOException {
        input();
        solve();
    }

    static void input() throws IOException {
        br = new BufferedReader(new InputStreamReader(System.in));
        for(int i = 0; i < 3; i++) {
            st = new StringTokenizer(br.readLine());
            for(int j = 0; j < 3; j++) {
                int n = Integer.parseInt(st.nextToken());
                input += n;
            }
        }
        map.put(input, 0);
    }

    static void solve() {
        Queue<String> q = new LinkedList<>();
        q.add(input);
        while(!q.isEmpty()) {
            String cur = q.poll();
            int cnt = map.get(cur);
            int loc = cur.indexOf("0");
            int x = loc / 3;
            int y = loc % 3;

            if(cur.equals(ans)) {
                System.out.println(cnt);
                break;
            }
            for(int i = 0; i < 4; i++) {
                int xx = dx[i] + x;
                int yy = dy[i] + y;

                if(xx < 0 || xx > 2 || yy < 0 || yy > 2) continue;

                int replaceIdx = xx*3+yy;
                //0과 스위칭 할 값
                char tmp = cur.charAt(replaceIdx);
                String next = cur.replace(tmp, 'c');
                next = next.replace('0', tmp);
                next = next.replace('c', '0');

                if(!map.containsKey(next)) {
                    q.add(next);
                    map.put(next, cnt+1);
                }
            }
        }
        if(!map.containsKey(ans)) System.out.println(-1);
    }

}

이번 문제는 자료구조를 유연하게 사용할 수 있어야 풀 수 있는 문제였다.

문제 자체는 딱봐도 bfs를 통해서 답을 구해내는 문제였으나 2차원 배열의 형태처럼 주어지기 때문에 2차원 배열을 이용해서 문제를 푼다면 메모리 초과로 인해서 난관에 빠질 수 있다.

 

어처피 주어진 배열의 크기는 3x3의 고정된 형태기 때문에 그냥 1차원배열의 형태로 사용해도 문제가 없다.

그렇기 때문에 나는 문자열 형태로 input을 변환시켜서 사용했다.

 

그리고 이 문제의 핵심인 배열의 상태 저장이다. 2차원 배열로 큐에 넣으면 당연히 메모리 초과가 발생하고 이는 매우 비효율적인 방법이다. 그렇기 때문에 큐의 자료형은 String으로 선언해주고 Map을 사용했다.

 

Map을 사용한 이유

 

1. key값을 현재 배열의 상태(문자열)로 저장한다면 상태 저장 및 중복 여부를 알 수 있다.

2. value값을 이동한 횟수로 저장한다면 최소 이동 횟수를 알 수 있다.

 

다음부터는 bfs 알고리즘 대로 큐에서 poll 한 상태의 배열에서 0의 위치를 뽑은 다음 인덱싱 처리를 해서 상, 하, 좌, 우별로 움직일 수 있는 곳인지 탐색 후 가능 한 위치로 배열의 상태를 업데이트 시켜준다.( 0과 바꿀 위치의 값을 스위칭) 그리고 업데이트 배열의 상태를 next에 초기화 후 map을 통해서 중복되지 않았다면 큐에 삽입한다. 그리고 맵에도 put 해주고 카운트도 하나 증감해준다.

마지막으로 큐가 다 빈 상태에서 map에 정답 key가 없다면 어떤 방향이든 도달하지 못한 것 이므로 -1을 출력해주면 된다.

 

풀이를 보지 못했다면 평생 못풀었을 것 같다... 정말 이런 유연한 사고는 언제쯤 길러질까 😓