백준 1525 퍼즐 Java

BFS를 이용한 완전 탐색을 통해 풀 수 있는 퍼즐 문제이다.

이 문제는 다른 BFS문제와는 다르게 0의 위치만 예제와 맞게 구현하면 안 되고

1부터 8까지의 수의 위치도 맞아야 하기 때문에 까다롭다.

 

먼저 편하게 풀기 위해 입력받은 값에서

초기 값인

1 2 3

4 5 6

7 8 0

으로 이동하는 문제로 바꿔서 풀고

2차원 배열은 까다롭기 때문에 1차원 배열로 바꾸어서 풀고

Map인터페이스를 이용해서 이동한 횟수를 저장하면서 풀어야 한다.

 

첫 번째 예제의 값

1 0 3 

4 2 5

7 8 6

을 예로 보면

1 0 3 4 2 5 7 8 6으로 바꾼다.

그리고 0 대신에 9를 넣어준다.

1 9 3 4 2 5 7 8 6

이 1차원 배열을

1 2 3 4 5 6 7 8 9로 바꾸는 데 걸린 최소 횟수를 출력하면 되는 문제가 된다.

 

9가 상하좌우로 이동 할 수 있기 때문에

큐를 사용한 BFS로 상하좌우 전부 이동시키면서

모든 경우의 수를 해보면 된다.

 

입력받은 수들을 1차원 배열로 저장하고 0을 9로 바꾸기 위한 코드는 이렇다.

int start = 0;
        for(int i=0; i<3; i++) {
            for(int j=0; j<3; j++) {
                int k = scan.nextInt();
                if(k == 0) { //0을 9로 바꿈
                    k = 9;
                }
                start = (start*10) +k; //2차원배열을 하나의 정수로 나타내기 위해서
            }
        }

설명이 굉장히 너저분하지만 코드를 읽어보면 충분히 이해할 수 있다.

import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;
import java.util.Queue;
import java.util.Scanner;
 
public class Q1525 {
 
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int start = 0;
        for(int i=0; i<3; i++) {
            for(int j=0; j<3; j++) {
                int k = scan.nextInt();
                if(k == 0) { //0을 9로 바꿈
                    k = 9;
                }
                start = (start*10) +k; //2차원배열을 하나의 정수로 나타내기 위해서
            }
        }
        
        Queue<Integer> q = new LinkedList<>();
        Map<Integer, Integer> m = new HashMap<>();
        int[] dx = {0, 0, 1, -1};
        int[] dy = {1, -1, 0, 0};
        
        m.put(start, 0);
        q.add(start);
        
        while(!q.isEmpty()) {
            int nowNum = q.poll();
            String now = String.valueOf(nowNum); 
            int nine = now.indexOf("9"); //9의 인덱스를 찾는다.
            int x = nine / 3; // 9가 2차원배열에서 몇 번째 행인지 계산
            int y = nine % 3; // 9가 2차원배열에서 몇 번째 열인지 계산
            for(int i=0; i<4; i++) {
                int nx = x+dx[i]; //이동할 상하좌우의 행 계산
                int ny = y+dy[i]; //이동할 상하좌우의 열 계산
                int move = nx*3+ny; //이동할 상하좌우의 1차원배열에서의 인덱스
                if (nx >= 0 && nx < 3 && ny >= 0 && ny < 3) {
                    StringBuilder next = new StringBuilder(now);
                    //9와 이동할 상하좌우 스왑하기
                    char temp = next.charAt(move);
                    next.setCharAt(move, '9'); //이동할 인덱스에 9를
                    next.setCharAt(nine, temp); //원래 9자리에 이동한 곳의 수를
                    int nextNum = Integer.parseInt(next.toString());
                    if(!m.containsKey(nextNum)) { //맵에 몇 번이동했는지 저장
                        m.put(nextNum, m.get(nowNum)+1);
                        q.add(nextNum);
                    }
                }
            }
        }
        if(m.containsKey(123456789)) {
            System.out.println(m.get(123456789));
        }
        else
            System.out.println(-1);
    }
}