[BOJ] 1525. 퍼즐

BFS를 이용하여 모든 경우를 탐색해는 방식으로 해결한 문제이다.

전체 퍼즐이 가지는 경우의 수가 9! 가지이므로 전체 경우를 다봐보는 경우를 생각해보았다. 일단 주어진 입력을 보았을때 0을 움직이는 BFS를 생각할수 있었다. 그렇게 하여 생각해낸것이 움직여서 나올 수 있는 2차원 배열 모양을 하나의 경우로 생각하였고, 0이 움직일수 있는 위치는 4방향이어서 하나의 2차원 배열에서 최대 4가지 모양을 가질수있다고 생각하였다. 그러한 모양에 대해 방문체크를 해주어야 했는데, 2차원 배열을 int의 형태로 만들어서 체크를 해주었다. 즉, 123456780 부터 087654321 까지의 숫자로 만들어주었고, 0이 맨앞에 오는 경우때문에 0을 9로 대체하여 구했다. visit을 만들때 문제가 있었는데 이땐 Map<Integer,Integer>를 이용하여 현재 2차원배열의 int형태를 가지고 있는지 체크하여 넣어주었다. 또한, 그움직였을때의 count값을 Map에 같이 넣어주어서 최종답을 출력할 수 있게 해주었다.

BFS의 까다로운 버전이라 다시한번 풀어볼 필요가 있는 문제인 것 같다.

package boj3;
 
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class Main_bj_1525_퍼즐 {
 
    static int[] di= {-1,0,1,0};
    static int[] dj= {0,1,0,-1};
    
    static int[][] map;
    
    static int answer;
    static Map<Integer, Integer> visit;
    static Queue<Integer> queue;
    
    public static void main(String[] args) throws Exception {
        BufferedReader br =new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st  =null;
        int start=0;
        
        for(int i=0;i<3;i++) {
            st=new StringTokenizer(br.readLine());
            for(int j=0;j<3;j++) {
                int num=Integer.parseInt(st.nextToken());
                if(num==0) {
                    start=start*10+9;
                }else {
                    start=start*10+num;
                }
            }
        }
        visit=new HashMap<>();
        queue=new LinkedList<>();
        
        visit.put(start, 0);
        queue.offer(start);
        answer=-1;
        map=new int[3][3];
        bfs();
        System.out.println(answer);
        
    }
    static void bfs() {
        
        while(!queue.isEmpty()) {
            int cur =queue.poll();
//            System.out.println(cur);
            int count=visit.get(cur);
            int curI=0;
            int curJ=0;
            
            if(cur==123456789) {
                answer=count;
                return;
            }
            
            //맵으로 변환
            for(int i=2;i>=0;i--) {
                for(int j=2;j>=0;j--) {
                    int num=cur%10;
                    if(num==9) {
                        curI=i;curJ=j;
                    }
                    map[i][j]=num;
                    cur=cur/10;
                }
            }
            
            for(int dir=0;dir<4;dir++) {
                int nextI=curI+di[dir];
                int nextJ=curJ+dj[dir];
                
                if(nextI<0 || nextI>=3 || nextJ<0 || nextJ>=3)
                    continue;
                
                //스왑
                map[curI][curJ]=map[nextI][nextJ];
                map[nextI][nextJ]=9;
                
                int num=0;
                for(int i=0;i<3;i++) {
                    for(int j=0;j<3;j++)
                        num=num*10+map[i][j];
                }
                
                if(!visit.containsKey(num)) {
                    visit.put(num, count+1);
                    queue.offer(num);
                }
                
                map[nextI][nextJ]=map[curI][curJ];
                map[curI][curJ]=9;
            }
            
            
            
        }
        
    }
}