백준 1525번 (java)

이 문제는 스스로 풀지 못했다.
1시간 가량 고민했는데
해답이 나오지 않아 다른 사람의 풀이를 보며 힌트를 얻어 풀어보았다.

이 문제는 BFS로 푸는 것조차 알아차리지 못했다.

접근

1. 이 문제는 최소 횟수를 묻는 문제였다.
2. 각각의 퍼즐 조각은 상하좌우로만 움직일 수 있다.
   -> 여기까지는 BFS()로 푸는게 문제가 된는게 없다.

하지만 어디에서 상태배열을 찾을까
상태배열 없이 BFS를 한다면 Queue에 무한 개의 데이터가 쌓여 스택 오버플로우가 발생한다.

따라서 Map을 이용할 것이다.
한번 등장한 형태의 퍼즐을 Queue에 쌓이지 못한다.
따라서 Queue에 쌓일 수 있는 것은 처음 등장한 Map의 key가 될 것이다.

그렇다면 이 3X3 배열을 Map의 key에 넣을 것인가에 대한 의문이 남는다.
배열을 넣지 않고 String 형태로 넣을 것이다.

그렇기 때문에 각 글자의 위치를 행렬의 위치로 변환하는 과정이 필요하다.
또한 그 반대로 필요하다. (행렬의 위치를 글자의 위치로 변환하는 과정)

// 글자 위치-> 행렬 (상하좌우 이동을 위해 필요하다)
int z_r = f.indexOf('0') / 3;
int z_c = f.indexOf('0') % 3;

for (int j = 0; j < 4; j++) {
        int t_r = z_r + cx[j];
         int t_c = z_c + cy[j];
         
         ...
          
 //행랼의 위치-> 글자 위치 (바뀌는 글자가 무엇인지 알기 위해 필요하다)
  char replace_char = f.charAt(t_r * 3 + t_c);

풀이

import java.util.*;
import java.io.*;

public class Main{

    static String target = "123456780";

    static int[] cx ={-1,1,0,0};
    static int[] cy ={0,0,-1,1};

    static Map<String,Integer> map; // 상테 배열과 같은 역할

    public static void main(String[] args) throws IOException {

        BufferedReader br=  new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        map = new HashMap<>();

        String init ="";
        for(int i=0;i<3;i++){
            StringTokenizer st = new StringTokenizer(br.readLine()," ");
            for(int j=0;j<3;j++){
                char in = st.nextToken().charAt(0);
                init+=in;
            }
        }
        map.put(init,0);
        int answer = BFS(init);

        bw.write(Integer.toString(answer));
        bw.flush();
        bw.close();
        br.close();

    }

    static int BFS(String init){
        Queue<String> Q = new LinkedList<>();
        Q.offer(init);
        while(!Q.isEmpty()){
            int size= Q.size();
            for(int i=0;i<size;i++) {
                String f = Q.poll();
                int move = map.get(f);
                int z_r = f.indexOf('0') / 3;
                int z_c = f.indexOf('0') % 3;

                if (f.equals(target)) {
                    return move;
                }
                for (int j = 0; j < 4; j++) {
                    int t_r = z_r + cx[j];
                    int t_c = z_c + cy[j];

                    if (t_r < 0 || t_r >= 3 || t_c < 0 || t_c >= 3) continue;


                    char replace_char = f.charAt(t_r * 3 + t_c);


                    String next = f.replace('0', 'c');
                    next = next.replace(replace_char, '0');
                    next = next.replace('c', replace_char);
                    if (!map.containsKey(next)) {
                        map.put(next, move + 1);
                        Q.offer(next);
                    }


                } //상하좌우 for
            }

        }//while

        return -1;

    }



}