[백준 Gold 2] 1525 퍼즐 - Java

문제링크 : https://www.acmicpc.net/problem/1525

1525번: 퍼즐

 

접근 과정 : 

• 3x3 표를 하나의 문자열로 이어서 String으로 관리
• 0의 위치에 따라서, 이동이 가능한 다음 String을 BFS로 탐색하고, "123456780"과 같으면 종료.
• 방문체크는 HashSet<String>으로 처리.

 

소스 코드 및 결과 :

package BOJ;

/* 
    퍼즐
*/

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

public class BOJ1525 {

    static int[] dx = { -1, 1, 0, 0 };
    static int[] dy = { 0, 0, -1, 1 };

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

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int[] zero = new int[2];

        String puzzle = "";
        String fin = "123456780";

        for (int i = 0; i < 3; i++) {
            String[] line = br.readLine().split(" ");

            for (int j = 0; j < 3; j++) {
                puzzle += line[j];

                if (line[j].equals("0")) {
                    zero[0] = i;
                    zero[1] = j;
                }
            }
        }

        if (puzzle.equals(fin)) {
            System.out.println(0);
            return;
        }

        Queue<Status> queue = new LinkedList<>();
        queue.add(new Status(puzzle, zero[0], zero[1]));
        HashSet<String> visit = new HashSet<>();
        visit.add(puzzle);

        int count = 0;

        while (!queue.isEmpty()) {

            count++;

            int size = queue.size();

            while (size-- > 0) {
                Status now = queue.poll();

                for (int i = 0; i < 4; i++) {
                    int nx = now.x + dx[i];
                    int ny = now.y + dy[i];

                    if (nx < 0 || nx >= 3 || ny < 0 || ny >= 3) {
                        continue;
                    }

                    char[] arr = now.puzzle.toCharArray();
                    arr[now.x * 3 + now.y] = arr[nx * 3 + ny];
                    arr[nx * 3 + ny] = '0';

                    String next = new String(arr);
                    if (!visit.contains(next)) {

                        if (next.equals(fin)) {
                            System.out.println(count);
                            return;
                        }

                        visit.add(next);
                        queue.add(new Status(next, nx, ny));
                    }
                }
            }

        }

        System.out.println(-1);

    }
}

class Status {
    String puzzle;
    int x;
    int y;

    public Status(String puzzle, int x, int y) {
        this.puzzle = puzzle;
        this.x = x;
        this.y = y;
    }
}

 

P.S 

BFS에서 0의 index(또는 좌표값)을 어떻게 관리하는지,

0과 다른 숫자의 자리 변경을 어떻게 하는지가

효율성을 결정할 것이라고 생각한다.

 

나도 좀 더 나은 방법을 찾아야 하는데...