[BOJ] 1525 - 퍼즐 JAVA

www.acmicpc.net/problem/1525

1525번: 퍼즐

문제

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

1	2	3
4	5	6
7	8

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

1		3
4	2	5
7	8	6

1	2	3
4		5
7	8	6

1	2	3
4	5
7	8	6

1	2	3
4	5	6
7	8

가장 윗 상태에서 세 번의 이동을 통해 정리된 상태를 만들 수 있다. 이와 같이 최소 이동 횟수를 구하는 프로그램을 작성하시오.

입력

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

출력

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

예제 입력 1

1 0 3

4 2 5

7 8 6

예제 출력 1

3

예제 입력 2

3 6 0

8 1 2

7 4 5

예제 출력 2

-1

 

 

 

 

 

 

 

풀이 1. (틀린 코드)

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

class Pair {
    int[][] arr;
    int dept;
    int zeroRow;
    int zeroCol;
    Pair(int[][] arr, int dept, int zeroRow, int zeroCol) {
        this.arr = arr;
        this.dept = dept;
        this.zeroRow = zeroRow;
        this.zeroCol = zeroCol;
    }
}

public class Main {
    static BufferedReader br = null;
    static StringTokenizer st = null;
    static int[][] map = null;
    static Map<String, Integer> check = null;

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

    static int ans = -1;

    public static void swap(int[][] arr, int row1, int col1, int row2, int col2) {
        int temp = arr[row1][col1];
        arr[row1][col1] = arr[row2][col2];
        arr[row2][col2] = temp;
    }

    public static String getStr(int[][] arr) {  // check를 위한 2차원 배열의 String 받기
        String str = "";
        for(int i = 0; i < arr.length; i++) {
            for(int j = 0; j < arr[i].length; j++) {
                str += String.valueOf(arr[i][j]);
            }
        }
        return str;
    }

    public static void putToCheck(int[][] arr) {  // 2차원 배열 형태에 대한 check를 String으로 기억
        String input = "";
        for(int i = 0; i < arr.length; i++) {
            for(int j = 0; j < arr[i].length; j++) {
                input += String.valueOf(arr[i][j]);
            }
        }
        check.put(input, 1);
    }

    public static void bfs(int zeroRow, int zeroCol) {
        Queue<Pair> que = new ArrayDeque<>();
        que.add(new Pair(map.clone(), 0, zeroRow, zeroCol));
        putToCheck(map);

        while(!que.isEmpty()) {
            Pair p = que.poll();
            int[][] temp = null;
            
            for(int i = 0; i < 4; i++) {
                temp = p.arr.clone();
                int nr = p.zeroRow + rArr[i];
                int nc = p.zeroCol + cArr[i];

                if(nr == 2 && nc == 2) {  // 다음 0의 위치가 [2][2]이면 완료
                    ans = p.dept + 1;
                    return;
                }

                if(-1 < nr && nr < 3 && -1 < nc && nc < 3) {  // 범위 체크
                    swap(temp, p.zeroRow, p.zeroCol, nr, nc);  // 0 위치 스왑
                    String str = getStr(temp);  // 바뀐 배열의 String
                    if(check.get(str) == null) {  // if(!check[temp])
                        que.add(new Pair(temp, p.dept + 1, nr, nc));
                        putToCheck(temp);  // check[temp] = true
                    }
                }
            }
        }
    }

    public static void main(String[] args) throws IOException {
        br = new BufferedReader(new InputStreamReader(System.in));
        map = new int[3][3];
        check = new HashMap<>();

        int zeroRow = 0, zeroCol = 0;
        for(int i = 0; i < 3; i++) {
            st = new StringTokenizer(br.readLine());
            for(int j = 0; j < 3; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
                if(map[i][j] == 0) {
                    zeroRow = i;
                    zeroCol = j;
                }
            }
        }

        if(map[2][2] == 0) {
            System.out.println(0);
            return;
        }
        bfs(zeroRow, zeroCol);
        System.out.println(ans);
    }
}

 

삽질을 꽤나 오랫동안 했다.

 

[2][2] == 0 으로 만드는 게 목적인 줄 알았는데 그게 아니었다. (심지어 이걸 구현하는 데 엄청 오래걸렸다)

퍼즐의 순서가 1, 2, 3, 4, 5, 6, 7, 8, 0 이 되도록 만들어야 한다.

 

하...

 

 

 

 

 

 

풀이 2. (정답 코드)

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

public class Main {
    static BufferedReader br = null;
    static StringTokenizer st = null;
    static Map<Integer, Integer> check = null;  // <검사 대상, dept> 방문여부와 dept를 한 번에 검사할 수 있다.

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

    public static void bfs(int init) {
        Queue<Integer> que = new ArrayDeque<>();
        que.add(init);
        check.put(init, 0);

        while (!que.isEmpty()) {
            int now = que.poll();
            String nowStr = String.valueOf(now);

            int indexOfNine = nowStr.indexOf("9");  // 일차원 배열 상에서 9의 인덱스
            int r = indexOfNine / 3;  // (핵심)
            int c = indexOfNine % 3;  // (핵심)

            for(int i = 0; i < 4; i++) {
                int nr = r + rArr[i];
                int nc = c + cArr[i];
                int move = nr * 3 + nc;  // (핵심) 일차원 배열 상에서 9가 이동할 인덱스

                if(-1 < nr && nr < 3 && -1 < nc && nc < 3) {
                    StringBuilder sb = new StringBuilder(nowStr);
                    char temp = sb.charAt(move);
                    sb.setCharAt(move, '9');
                    sb.setCharAt(indexOfNine, temp);

                    int next = Integer.parseInt(sb.toString());
                    if(check.get(next) == null) {
                        check.put(next, check.get(now) + 1);
                        que.add(next);
                    }
                }
            }
        }
    }

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

        int init = 0;
        for(int i = 0; i < 3; i++) {
            st = new StringTokenizer(br.readLine());
            for(int j = 0; j < 3; j++) {
                int input = Integer.parseInt(st.nextToken());
                if(input == 0) input = 9;  // 이차원 배열을 하나의 숫자로 표현하기 위해 0을 9로 바꾼다.
                init = (init * 10) + input;  // 0을 그대로 사용해버리면 나중에 인덱스가 꼬일 수 있음.
            }
        }

        bfs(init);
        if(check.get(123456789) == null) {
            System.out.println(-1);
        }else {
            int ans = check.get(123456789);
            System.out.println(ans);
        }
    }
}

 

삽질 1.

나도 처음에는 배열을 int로 표현하려고 했었지만 0이 들어가면 제대로 된 값을 구할 수가 없어져서 시간이 좀 느려지더라도 String으로 처리한 거였는데.. 그냥 0을 9로 바꿔버리면 아주 간단히 해결되는 문제였다.

(그리고 아마 String 그대로 사용했으면 그건 시간초과로 틀렸을 듯?)

 

 

삽질 2.

swap을 할 때 원본 배열값을 유지하기 위해 나름대로 Deep Copy를 하겠다고 clone()을 사용했다.

그런데, 분명 clone()은 딥카피로 배열을 복사해주는 함수인데.. 자꾸 원본 배열까지 수정이 되는 문제가 발생했다.

 

알고보니 2차원 배열을 온전히 딥카피 해주려면 2차원 배열의 모든 행을 하나하나 전부 clone() 해줘야 하는 것이었다.

2차원 배열의 원소인 1차원 배열은 Object이기 때문에 원래 값이 유지되었던 것이다. 그러니 당연히 원본 값도 같이 수정이 되지..

 

 

삽질 3.

딥카피도 문제였지만 사실 2차원 배열 자체를 쓸 필요가 없었다.

 

2차원 배열을 1차원 배열 형태로 표현했을 때, 2차원 배열의 인덱스에 대응되는 1차원 배열이 인덱스를 뽑아낼 수 있는 방법이 있었다.

간단한 수식으로 해결할 수 있었는데 역시 수학멍청이답게 전혀 생각하지 못하고 있다가 구글링을 통해 알게 됐다.

 

 

삽질 4.

그리고 굳이 Pair를 사용할 필요도 없었다. 

(배열, dept, zeroRow, zeroCol 다 때려박은 순간부터 Pair라는 이름도 모순이 돼버렸지만)

 

Map을 사용해서 checking과 dept를 한 번에 다룰 수 있었다.

(해당 key의 value가 없으면 방문하지 않은 것. 있다면 그 value가 해당 key의 dept())

 

 

 

 

 

 

아.. 너무 힘들다...