[백준 JAVA] 16954 움직이는 미로 탈출

16954 움직이는 미로 탈출

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

문제설명

캐릭터가 벽이 이동하는 가운데 목표 위치로 이동할 수 있는지 계산

접근방식

O(1) 상수 시간복잡도

 

체스판의 크기가 고정되어 있으며, BFS 탐색과 벽 이동 처리 모두 상수 시간 내에 처리된다.

 

문제 조건 분석 과정

• 체스판 크기: 8x8 (고정 크기)
• 캐릭터 이동: 인접한 8 방향 또는 대각선으로 이동 가능
• 벽 이동: 벽은 매 초마다 아래로 한 칸 이동

매 초마다 벽을 아래로 한 칸 이동시키며, 벽이 사라지면 새로운 벽이 추가된다.

• 캐릭터의 위치를 BFS(너비 우선 탐색)를 사용하여 탐색한다.
• BFS는 현재 위치에서 인접한 모든 위치를 탐색하며 이동한다.

전체코드

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

public class Main {
    // 상하좌우 이동을 위한 방향 배열
    static final int[] dx = {1, -1, 0, 0};
    static final int[] dy = {0, 0, 1, -1};

    // 말의 L자 이동을 위한 방향 배열
    static final int[] horseDx = {2, 2, -2, -2, 1, 1, -1, -1};
    static final int[] horseDy = {1, -1, 1, -1, 2, -2, 2, -2};

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

        // 첫 번째 줄에서 K 값을 읽어옴 (원숭이의 말과 같은 L자 이동 횟수)
        StringTokenizer st = new StringTokenizer(br.readLine());
        int K = Integer.parseInt(st.nextToken());

        // 두 번째 줄에서 W와 H 값을 읽어옴 (그리드의 너비와 높이)
        st = new StringTokenizer(br.readLine());
        int W = Integer.parseInt(st.nextToken());
        int H = Integer.parseInt(st.nextToken());

        // H x W 크기의 그리드를 읽어옴
        int[][] grid = new int[H][W];
        for (int i = 0; i < H; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < W; j++) {
                grid[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        // visited 배열을 초기화 (방문 여부와 최단 거리를 저장)
        // visited[x][y][k]는 좌표 (x, y)에 말과 같은 L자 이동이 k번 남았을 때의 최단 거리
        int[][][] visited = new int[H][W][K + 1];
        for (int[][] row : visited) {
            for (int[] cell : row) {
                Arrays.fill(cell, -1);
            }
        }

        // BFS 탐색을 위한 큐
        Queue<int[]> queue = new LinkedList<>();
        // 시작점 (0, 0), 말과 같은 L자 이동 횟수 K, 현재 이동 거리 0
        queue.add(new int[]{0, 0, K, 0});
        visited[0][0][K] = 0;

        // BFS 탐색 시작
        while (!queue.isEmpty()) {
            int[] current = queue.poll();
            int x = current[0]; // 현재 x 좌표
            int y = current[1]; // 현재 y 좌표
            int remainingHorseMoves = current[2]; // 남은 말과 같은 L자 이동 횟수
            int moves = current[3]; // 현재까지 이동한 거리

            // 목표 지점에 도착하면 최단 거리 출력
            if (x == H - 1 && y == W - 1) {
                System.out.println(moves);
                return;
            }

            // 상하좌우 이동
            for (int i = 0; i < 4; i++) {
                int nx = x + dx[i];
                int ny = y + dy[i];
                // 이동 가능한 위치인지 확인
                if (nx >= 0 && ny >= 0 && nx < H && ny < W && grid[nx][ny] == 0 && visited[nx][ny][remainingHorseMoves] == -1) {
                    visited[nx][ny][remainingHorseMoves] = moves + 1;
                    queue.add(new int[]{nx, ny, remainingHorseMoves, moves + 1});
                }
            }

            // 남아 있는 말과 같은 L자 이동 횟수가 있는 경우
            if (remainingHorseMoves > 0) {
                // 말의 이동을 적용하여 새로운 위치 탐색
                for (int i = 0; i < 8; i++) {
                    int nx = x + horseDx[i];
                    int ny = y + horseDy[i];
                    // 이동 가능한 위치인지 확인
                    if (nx >= 0 && ny >= 0 && nx < H && ny < W && grid[nx][ny] == 0 && visited[nx][ny][remainingHorseMoves - 1] == -1) {
                        visited[nx][ny][remainingHorseMoves - 1] = moves + 1;
                        queue.add(new int[]{nx, ny, remainingHorseMoves - 1, moves + 1});
                    }
                }
            }
        }

        // 목표 지점에 도달할 수 없는 경우 -1 출력
        System.out.println(-1);
    }
}