[백준] 1525: 퍼즐 - JAVA

in Algorithm on 자료 구조

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

풀이

3x3 표의 퍼즐을 맞추는데 최소 이동 횟수를 구하는 문제였다.

빈칸은 0으로 주어지고 0의 상하좌우에 있는 숫자를 0위치로 이동시킨다.

0을 기준으로 상하좌우를 탐색하여 숫자를 바꿔주고, 그렇게 만들어진 배치를 방문처리하였다.

이때 방문처리를 String으로 하였는데, 메모리제한때문이었다.

숫자들을 이어붙여 String으로 만들었고, String의 indexOf 메서드를 이용하여 위치를 찾아 좌표를 구했다.

Map에 String과 이동횟수를 저장하며 방문처리를 해줬고, “123456780”이 된다면 퍼즐의 완성이므로 Map에서 이동횟수를 꺼내어 출력했다.

메모리: 122456KB

시간: 1048ms

언어: Java 11

코드

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

public class Main {

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

        String org = "";
        for (int i = 0; i < 3; i++) {
            String tmp = br.readLine().replace(" ", "");
            org += tmp;
        }

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

    static int[][] vector = { { 1, 0 }, { -1, 0 }, { 0, 1 }, { 0, -1 } };

    private static int bfs(String original) {
        Queue<String> queue = new LinkedList<>();
        Map<String, Integer> map = new HashMap<>();

        queue.add(original);
        map.put(original, 0);

        while (!queue.isEmpty()) {
            String s = queue.poll();

            if (s.equals("123456780")) {
                return map.get(s);
            }

            int idx = s.indexOf('0');
            int r = idx / 3;
            int c = idx % 3;

            for (int i = 0; i < 4; i++) {
                int nr = r + vector[i][0];
                int nc = c + vector[i][1];

                if (nr < 0 || nc < 0 || nr > 2 || nc > 2) {
                    continue;
                }

                int nidx = nr * 3 + nc;
                char tmp = s.charAt(nidx);
                String next = s.replace(tmp, 'x');
                next = next.replace('0', tmp);
                next = next.replace('x', '0');

                if (!map.containsKey(next)) {
                    queue.add(next);
                    map.put(next, map.get(s) + 1);
                }
            }
        }

        return -1;
    }

}