[알고리즘] 백준 > #1525. 퍼즐

문제링크

백준 #1525. 퍼즐

풀이방법

두가지 풀이방법으로 접근했었다. 둘 다 BFS를 사용한다는 공통점이 있었지만, 첫번째 방법은 table정보를 2차원 배열 그대로 저장했었다. 당연히 메모리초과가 났다 ^0^

이걸 어떻게 메모리를 줄일 수 있을까.. 고민했다! 모든 움직인 케이스를 가지고 있었야하는건 분명했다. 2차원배열을 어떻게 줄일까에 집중했고 그냥 String으로 저장하자는 결론이 나왔다. 말그대로 [[1, 2, 3], [4, 5, 6], [7, 8, 0]]를 123456780으로 저장하는거다!

(String 내 index) <-> (이차원배열 내 index) 변환은 /3, %3 연산이면 충분했다.

• (String 내 index) -> (이차원배열 내 index)

int emptyIndex = sb.indexOf("0");
int emptyY = emptyIndex / 3;
int emptyX = emptyIndex % 3;

• (String 내 index) <- (이차원배열 내 index)

sb.setCharAt(emptyY * 3 + emptyX, '0');

코드

import java.util.*;
public class BOJ1525 {

    private static int[] dy = {-1, +1, 0, 0};
    private static int[] dx = {0, 0, +1, -1};

    private static final String SORTED = "123456780";

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int[][] initTable = new int[3][3];
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) initTable[i][j] = sc.nextInt();
        }

        Queue<TableInfo> q = new LinkedList<>();
        q.offer(new TableInfo(tableToString(initTable), 0));

        HashSet<String> set = new HashSet<>();

        int result = -1;
        while (!q.isEmpty()) {
            TableInfo head = q.poll();
            if (head.table.equals(SORTED)) {
                result = head.time;
                break;
            }

            StringBuilder sb = new StringBuilder(head.table);

            for (int i = 0; i < 4; i++) {
                int emptyIndex = sb.indexOf("0");
                int emptyY = emptyIndex / 3;
                int emptyX = emptyIndex % 3;
                int swapY = emptyY + dy[i];
                int swapX = emptyX+ dx[i];

                if (isInTable(swapY, swapX)) {
                    char swapValue = sb.charAt(swapY * 3 + swapX);

                    sb.setCharAt(emptyY * 3 + emptyX, swapValue);
                    sb.setCharAt(swapY * 3 + swapX, '0');

                    String currentTableString = sb.toString();

                    if (!set.contains(currentTableString)) {
                        q.offer(new TableInfo(currentTableString, head.time + 1));
                        set.add(currentTableString);
                    }

                    sb.setCharAt(emptyY * 3 + emptyX, '0');
                    sb.setCharAt(swapY * 3 + swapX, swapValue);
                }
            }
        }

        System.out.print(result);
    }

    private static boolean isInTable(int y, int x) {
        return (y >= 0) && (y < 3) && (x >= 0) && (x < 3);
    }

    private static String tableToString(int[][] table) {
        String tableString = "";
        for (int i = 0; i < 3; i++) for (int j = 0; j < 3; j++) tableString += table[i][j];
        return tableString;
    }
}

class TableInfo {
    public String table;
    public int time;

    public TableInfo(String table, int time) {
        this.table = table;
        this.time = time;
    }
}