[알고리즘] - 백준 1525번 : 퍼즐 (JAVA)

🎯 문제

문제 풀러가기

🎯 입력, 출력

🚀 풀이방법

BFS를 이용한 완전 탐색 문제입니다.

입력으로는 2차원 배열처럼 주어지는데 이 문제의 핵심은 2차원 배열처럼 곧이 곧대로 입력받아서 문제를 푸는 것보다
어차피 3X3형태의 배열이니 1차원 배열처럼 나열해서 푸는 것이 효율적이었습니다.
0은 9로 바꾸어 입력 받았습니다.

이렇게 입력을 받고 나서 문제의 핵심 로직은 Map을 사용하는 것입니다.
Map의 Key로는 일차원 배열(현재까지 갱신된 값)로 , Value로는 현재까지 이동한 횟수로 해서 문제를 풀어 나가면 됩니다.

map을 사용하는 예를 하나 들어보겠습니다.
1 2 3
5 9 6
4 7 8
이라는 입력이 주어졌을 때,
일단은
123596478 의 형태로 만들어 줍니다.
9와 6을 바꿔보죠
이때 map에는 Key로는 123569478 이 Value로는 현재 이동한 수가 1이니 1을 put해줍니다.

이렇게 상하좌우를 완전 탐색하며 map과 함께 문제를 풀어 나가면 됩니다.

🚀 CODE

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

public class Main {
    static int[] dx=new int[]{-1,0,1,0};
    static int[] dy=new int[]{0,-1,0,1};

    public static void main(String[] args) throws Exception{
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        StringBuilder start=new StringBuilder();

	// 입력받는 부분
        for(int i=0;i<3;i++) {
            StringTokenizer st=new StringTokenizer(br.readLine()," ");
            for (int j = 0; j < 3; j++) {

                String temp=st.nextToken();
                if(temp.equals("0")) {
                    start.append("9");
                }
                else
                    start.append(temp);
            }
        }

        Queue<String> dq=new LinkedList<>();
        Map<String,Integer> m=new HashMap<>();
        dq.offer(start.toString());
        m.put(start.toString(),0);

        while(!dq.isEmpty()){
            String present=dq.poll();
            int nineLoc=present.indexOf("9");
            int x=nineLoc/3;
            int y=nineLoc%3;

            for(int i=0;i<4;i++){
                int xx=dx[i]+x;
                int yy=dy[i]+y;
                int move=xx*3+yy;
                if(xx>=0 && xx<3 && yy>=0 && yy<3){
                    StringBuilder next=new StringBuilder(present);
                    char temp=next.charAt(move);
                    next.setCharAt(nineLoc,temp);
                    next.setCharAt(move,'9');
                    String nextStr=next.toString();
                    if(!m.containsKey(nextStr)){
                        dq.offer(nextStr);
                        m.put(nextStr,m.get(present)+1);
                    }
                }
            }
        }

        if(m.containsKey("123456789")){
            System.out.println(m.get("123456789"));
        }
        else{
            System.out.println(-1);
        }

    }
}

👏 정답

😍 이상으로 포스팅을 마치겠습니다. 감사합니다 :)