[백준] 1525 퍼즐

1. 문제

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

1525번: 퍼즐

2. 접근방법

가장 빠른 순서를 구해야 하고 분기가 여러가지 이므로 bfs로 풀이했다.

 

다만 일반적인 bfs와 다른 점은 3*3 배열을 visit 체크 해야 하기 때문에

hash와 set을 이용하여 배열을 integer로 변경하여 처리 해줬다.

 

최종 배열과의 비교도 똑같이 hash값으로 변경하여 비교하였다.

 

이것만 유의해서 풀이하면 어렵지 않게 풀이할 수 있다.

3. 자바 코드

package backjoon;

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

public class P1525퍼즐 {

    static class node{
        int [][] map;
        Point zero;
    }
    static int dr[] = new int [] {-1,1,0,0};
    static int dc[] = new int [] {0,0,1,-1};
    static HashSet<Integer> visit = new HashSet<>();
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int result [][] = new int [][] {{1,2,3},{4,5,6},{7,8,0}};
        int resultHash = getHash(result);
        int arr[][] = new int[3][3];
        Point zero = new Point();
        for(int i = 0 ; i < 3 ; i++){
            StringTokenizer st = new StringTokenizer(br.readLine());
            for(int j = 0 ; j < 3 ; j++){
                arr[i][j] = Integer.parseInt(st.nextToken());
                if(arr[i][j] == 0){
                    zero = new Point(i,j);
                }
            }
        }
        if(resultHash == getHash(arr)){
            System.out.println(0);
            return;
        }

        node first = new node();
        Queue<node> que = new LinkedList<>();
        first.zero = zero;
        first.map = arr;
        que.add(first);
        int count = 0;
        while(!que.isEmpty()){
            int size = que.size();
            count++;
            while(size-- > 0) {
                node now = que.poll();
                for (int i = 0; i < 4; i++) {
                    int row = now.zero.x + dr[i];
                    int col = now.zero.y + dc[i];
                    if (row < 0 || col < 0 || row >= 3 || col >= 3)
                        continue;
                    int[][] map = deepCopy(now.map);
                    map[now.zero.x][now.zero.y] = map[row][col];
                    map[row][col] = 0;
                    int hashValue = getHash(map);
                    if (!visit.add(hashValue))
                        continue;
                    if(hashValue == resultHash) {
                        System.out.println(count);
                        return;
                    }
                    node n = new node();
                    n.map = map;
                    n.zero = new Point(row, col);
                    que.add(n);
                }
            }
        }
        System.out.println(-1);
    }

    static int getHash(int [][] map){
        int gop = 1;
        int multi = 0;
        for(int i = 0 ; i < 3 ; i++){
            for(int j = 0 ; j < 3 ; j++){
                multi += map[i][j] * gop;
                gop *= 10;
            }
        }
        return multi;
    }
    static int [][] deepCopy(int [][] map){
        int [][] newMap = new int[3][3];
        for(int i = 0 ; i < 3 ; i++){
            for(int j = 0 ; j < 3 ; j++){
                newMap[i][j] = map[i][j];
            }
        }
        return newMap;
    }
}

4. 마치며

map이 크지 않아서 dfs로도 풀이 가능 할 것 같다.

코드도 훨씬 깔끔해질듯.