[백준]#1525 퍼즐

SeungBird·2020년 8월 28일
0

⌨알고리즘(백준)

목록 보기
101/401
post-thumbnail

문제

3×3 표에 다음과 같이 수가 채워져 있다. 오른쪽 아래 가장 끝 칸은 비어 있는 칸이다.

123
456
78

어떤 수와 인접해 있는 네 개의 칸 중에 하나가 비어 있으면, 수를 그 칸으로 이동시킬 수가 있다. 물론 표 바깥으로 나가는 경우는 불가능하다. 우리의 목표는 초기 상태가 주어졌을 때, 최소의 이동으로 위와 같은 정리된 상태를 만드는 것이다. 다음의 예를 보자.

13
425
786
123
45
786
123
45
786
123
456
78

가장 윗 상태에서 세 번의 이동을 통해 정리된 상태를 만들 수 있다. 이와 같이 최소 이동 횟수를 구하는 프로그램을 작성하시오.

입력

세 줄에 걸쳐서 표에 채워져 있는 아홉 개의 수가 주어진다. 한 줄에 세 개의 수가 주어지며, 빈 칸은 0으로 나타낸다.

출력

첫째 줄에 최소의 이동 횟수를 출력한다. 이동이 불가능한 경우 -1을 출력한다.

예제 입력 1

1 0 3
4 2 5
7 8 6

예제 출력 1

3

예제 입력 2

3 6 0
8 1 2
7 4 5

예제 출력 2

-1

풀이

이 문제는 Hashset을 이용해서 빠른 으로 BFS 알고리즘을 이용해서 풀 수 있다.

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

public class Main {
    static HashSet<Integer> hs = new HashSet<>();
    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));
        StringBuffer sb = new StringBuffer();

        for(int i=0; i<3; i++) {
            String[] input = br.readLine().split(" ");
            for(int j=0; j<3; j++) {
                sb.append(input[j]);
            }
        }

        int input = Integer.parseInt(sb.toString());
        bfs(input);
    }

    static void bfs(int input) {
        Queue<Pair> queue = new LinkedList<>();
        hs.add(input);
        queue.add(new Pair(0, input));

        while(!queue.isEmpty()) {
            Pair p = queue.poll();
            int num = p.str;

            if(num==123456780) {
                System.out.println(p.t);
                return ;
            }

            String str = Integer.toString(num);
            if(str.length()==8)
                str = 0+str;

            int index = str.indexOf('0');
            int x = index/3;
            int y = index%3;

            for(int i=0; i<4; i++) {
                int X = x+dx[i];
                int Y = y+dy[i];

                if(X<0 || X>=3 || Y<0 || Y>=3)
                    continue;

                int target = 3*X+Y;
                String s2 = swap(str, index, target);
                int swaped = Integer.parseInt(s2);

                if(hs.add(swaped)) {
                    queue.add(new Pair(p.t+1, swaped));
                }
            }
        }
        System.out.println(-1);
    }

    static String swap(String str, int index1, int index2) {
        StringBuilder sb = new StringBuilder(str);
        sb.setCharAt(index1, str.charAt(index2));
        sb.setCharAt(index2, str.charAt(index1));

        return sb.toString();
    }

    static class Pair {
        int t;
        int str;

        public Pair(int t, int str) {
            this.t = t;
            this.str = str;
        }
    }
}
profile
👶🏻Jr. Programmer

0개의 댓글