[백준알고리즘 -1525] 퍼즐 - java (BFS)

요즘 플젝 거의 리팩토링 단계, 또는 노가다 단계라서 업로드할 일이 별로 없다 ㅠ___ㅠ

절대 스프링을 소홀하게 하고있는 것이 아닌데 믿어주새오 

문제로 돌아가서, 

3x3 배열을 1차원 배열로 바꾼 뒤 int형으로 처리하였다

0은 9로 바꾸었고 정수가 123456789일 때 bfs를 종료하도록 하였다.

import java.io.IOException;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Map;
import java.util.Queue;
import java.util.Scanner;
import java.util.Set;

class Main{
       public static void main(String[] args) throws IOException {
    	   Scanner scan=new Scanner(System.in);
    	   int puzzle=0;
    	   int flag=100000000;

    	   for(int i=0; i<9; i++) {
    		   int n=scan.nextInt();
    		   if(n!=0) 
    			   puzzle+=n*flag;
    		   else
    			   puzzle+=9*flag;
    		   flag/=10;
    	   }
    	   
    	   Map<Integer,Integer> dist=new HashMap<>();
    	   
    	   Queue<Integer> queue=new LinkedList<>();
    	   int pn=puzzle;
    	   queue.add(pn);
    	   dist.put(pn, 0);
    	   while(!queue.isEmpty()) {
    		   int now=queue.poll();
    		   int nw=-1;
    		   if(now==123456789) {
    			   System.out.println(dist.get(now));
    			   return;
    		   }
    		   //현재 9의 위치	
    		   nw=Integer.toString(now).indexOf('9');
    		   String str=Integer.toString(now);
    		   
    		   StringBuilder builder = new StringBuilder(str);

    		   if(nw-3>=0 ) {
    			   //위로 이동 가능
    			   builder.setCharAt(nw, str.charAt(nw-3));
    			   builder.setCharAt(nw-3, '9');
    			   int an=Integer.parseInt(builder.toString());
    			   if(dist.get(an)==null) {
    				   queue.add(an);
    				   dist.put(an, dist.get(now)+1);
    			   }
    		   }
    		   
    		   if(nw%3!=2) {
    			   //오른쪽으로 이동 가능
    			   builder = new StringBuilder(str);
    			   builder.setCharAt(nw, str.charAt(nw+1));
    			   builder.setCharAt(nw+1, '9');
    			   int an=Integer.parseInt(builder.toString());
    			   if(dist.get(an)==null) {
    				   queue.add(an);
    				   dist.put(an, dist.get(now)+1);
    			   }
    		   }
    		   
    		   if(nw%3!=0) {
    			   //왼쪽으로 이동 가능
    			   builder = new StringBuilder(str);
    			   builder.setCharAt(nw, str.charAt(nw-1));
    			   builder.setCharAt(nw-1, '9');
    			   int an=Integer.parseInt(builder.toString());
    			   if(dist.get(an)==null) {
    				   queue.add(an);
    				   dist.put(an, dist.get(now)+1);
    			   }
    		   }

    		   

    		   if(nw+3<9) {
    			   //아래쪽으로 이동 가능
    			   builder = new StringBuilder(str);
    			   builder.setCharAt(nw, str.charAt(nw+3));
    			   builder.setCharAt(nw+3, '9');
    			   int an=Integer.parseInt(builder.toString());
    			   if(dist.get(an)==null) {
    				   queue.add(an);
    				   dist.put(an, dist.get(now)+1);
    			   }
    		   }

    	   }
    	   System.out.println(-1);
       }

       
}

시간 안에 해결되긴 하지만 속도가 쪼금 아쉽다.

다른분들 코드보고 수정좀 해봐야겠다.

그리고 StringBuilder 공부하기!!!!!