BOJ#1525 퍼즐

BOJ#1525 퍼즐

* 문제

https://www.acmicpc.net/problem/1525

* 풀이

종만북을 참고하여 풀었습니다.

To-Do : bfs, 양방향탐색, dfs 방법으로 각각 풀어보기

저는 이번에 bfs와 비트마스크를 이용해보았습니다.

맵은 하나의 정점으로 볼 수 있습니다.  (총 정점의 수는 9! : 1부터 9까지 순서대로 나열하는 경우의 수와 같다)

그리고 상하좌우 4방향으로 이동할 수 있으니, 한 정점에서 최대 4개의 정점과 연결될 수 있습니다.

즉, 주어진 정점에서 시작하여 4방향 탐색을 해나가면서 목표를 찾으면 되겠습니다.

문제는 어떻게 중복 방문을 체크하고 처리할 것인지 생각해봐야 합니다.

저는 비트마스크를 이용해보았습니다.

각 값은 0부터 8사이의 값이므로, 각 값은 4비트를 사용하면 저장할 수 있습니다.

비트마스크를 사용하여 맵의 상태를 long 변수에 담아봅시다.

1		3
4	2	5
7	8	6

위 맵을 비트마스크를 이용하여 표현해보면

000100000011010000100101011110000110 이 됩니다.

보기쉽게 분리해보면

0001 0000 0011

0100 0010 0101

0111 1000 0110

, 이 상태에서 4방향 탐색을 해봅시다. 현재 빈칸의 위치가 row=0, col=1이므로 좌/우/아래의 3가지 탐색만 가능할 것입니다.

1. 좌

0000 0001 0011 

0100 0010 0101

0111 1000 0110

2. 우

0001 0011 0000 

0100 0010 0101 

0111 1000 0110

3. 아래

0001 0010 0011 

0100 0000 0101 

0111 1000 0110

---

* 나의 코드

https://github.com/stack07142/BOJ/blob/master/BOJ%231525_Puzzle/src/Main.java

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

/**
 * BOJ#1525 퍼즐
 * https://www.acmicpc.net/problem/1525
 */

public class Main {

    static final int SIZE = 3;

    // left, up, right, down
    static final int[] dRow = {0, -1, 0, 1};
    static final int[] dCol = {-1, 0, 1, 0};
    static final long[] dShift = {-4, -12, 4, 12};

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

        int row = -1, col = -1;
        // 현재 map, 종료 map
        long state = 0L, endState = 0L;
        HashSet<Long> discovered = new HashSet<>();

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        for (int i = 0; i < SIZE; i++) {

            StringTokenizer st = new StringTokenizer(br.readLine());

            for (int j = 0; j < SIZE; j++) {

                int number = Integer.parseInt(st.nextToken());

                if (number == 0) {

                    row = i;
                    col = j;
                }

                state <<= 4;
                state |= number;
            }
        }

        for (int i = 1; i < 9; i++) {

            endState <<= 4;
            endState |= i;
        }
        endState <<= 4;

        // solve - bfs

        // 이동횟수
        int cnt = -1;

        Queue<Point> queue = new LinkedList<>();

        queue.add(new Point(row, col, state));
        discovered.add(state);

        while (!queue.isEmpty()) {

            cnt++;

            int size = queue.size();
            for (int i = 0; i < size; i++) {

                Point u = queue.poll();

                // 종료 조건
                if (u.state == endState) {

                    System.out.println(cnt);
                    return;
                }

                // 4방향 탐색
                for (int j = 0; j < 4; j++) {

                    int nextRow = u.row + dRow[j];
                    int nextCol = u.col + dCol[j];

                    // map 범위를 벗어나는 경우
                    if (nextRow < 0 || nextRow > 2 || nextCol < 0 || nextCol > 2) continue;

                    // nextState 계산

                    // 제거할 퍼즐 조각 위치 (0~8) : nextRow, nextCol -> nextPos
                    long nextPos = 8 - ((nextRow * 3) + nextCol);

                    // 제거할 퍼즐 조각
                    long piece = u.state & (15L << (nextPos * 4));

                    // 제거한다
                    long nextState = u.state - piece;

                    // 제거한 퍼즐 조각을 현재 위치에 추가한다
                    if (dShift[j] > 0) piece <<= dShift[j];
                    else piece >>= -dShift[j];

                    nextState += piece;

                    // nextState를 이미 방문한 경우
                    if (discovered.contains(nextState)) continue;

                    // nextState를 방문하지 않은 경우
                    discovered.add(nextState);
                    queue.add(new Point(nextRow, nextCol, nextState));
                }
            }
        }

        System.out.println(-1);
    }
}

class Point {

    int row, col;
    long state;

    Point(int row, int col, long state) {

        this.row = row;
        this.col = col;
        this.state = state;
    }
}