자바(Java) 백준 16954 움직이는 미로 탈출 풀이

문제

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

16954번: 움직이는 미로 탈출

풀이

bfs로 문제를 풀었습니다.

• 먼저 움직인 횟수에 따른 체스판 모양을 구해야 합니다.
  • 한 번 움직일 때 마다 체스판이 밑으로 움직이게 됩니다.
  • 맨 밑에 있는 줄은 사라집니다.
  • 맨 위에 있는 줄은 벽이 없는 상태로 생성됩니다.
  • 체스판은 8 * 8 이므로 총 9가지의 체스판 모양이 생기며 8번 이상 움직인 경우에 체스판에 모든 벽이 사라지는 상태가 됩니다.
• 체스의 현재 위치와 움직인 횟수를 Point 클래스에 저장해주고 큐에서 꺼내 사용합니다.
• 체스는 대각선 포함 8가지 방향으로 움직일 수 있고 가만히 있을 수 있습니다.
• 방문체크는 현재 체스판의 모양과 같은 경우에 할 수 있습니다.
• 따라서 3차원 배열로 9가지 체스판 모양에 대해서 방문체크를 해주면 됩니다.

코드

package code;

import java.io.*;
import java.util.LinkedList;
import java.util.Queue;

public class Backjoon16954 {

    static char[][][] board = new char[9][8][8]; // 움직일 때 마다 벽이 움직이므로 모든 벽이 사라지는 9번째 턴까지 체스판을 저장합니다.
    static boolean[][][] visited = new boolean[9][8][8]; // 방문체크도 벽의 모양에 따라 9가지로 체크해줍니다.
    static int[] dx = {1, -1, 0, 0, 1, 1, -1, -1, 0};
    static int[] dy = {0, 0, 1, -1, 1, -1, 1, -1, 0};

    static class Point {
        int x;
        int y;
        int count;

        public Point(int x, int y, int count) {
            this.x = x;
            this.y = y;
            this.count = count;
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        for (int i = 0; i < 8; i++) {
            char[] chars = br.readLine().toCharArray();
            for (int j = 0; j < 8; j++) {
                board[0][i][j] = chars[j];
            }
        }

        // 체스판의 모양은 모든 벽이 사라지는 경우까지 총 9가지가 존재합니다. 9가지 체스판 모양을 생성합니다.
        for (int i = 1; i <= 8; i++) {
            for (int j = i - 1; j >= 0; j--) {
                board[i][j] = new char[]{'.', '.', '.', '.', '.', '.', '.', '.'};
            }

            for (int j = i; j < 8; j++) {
                board[i][j] = board[i - 1][j - 1].clone();
            }
        }

        bw.write(bfs());
        bw.flush();
        bw.close();
    }

    static int bfs() {
        Queue<Point> queue = new LinkedList<>();
        queue.offer(new Point(7, 0, 0));

        while (!queue.isEmpty()) {
            Point point = queue.poll();

            // 현재 벽 모양을 체크하기 위한 변수입니다.
            int count = Math.min(point.count, 8);

            if (point.x == 0 && point.y == 7) {
                return 1;
            }

            if (board[count][point.x][point.y] == '#') {
                continue;
            }

            for (int d = 0; d < 9; d++) {
                int newX = point.x + dx[d];
                int newY = point.y + dy[d];

                if (newX < 0 || newX >= 8 || newY < 0 || newY >= 8 || board[count][newX][newY] == '#' || visited[count][newX][newY]) {
                    continue;
                }

                visited[count][newX][newY] = true;
                queue.offer(new Point(newX, newY, count + 1));
            }
        }

        return 0;
    }
}