[Java] 난이도 - 중 / DP 문제

🎈 문제

이 게임은 시작점에서 도착점까지 이동하는 게임으로, 길이 미로로 되어있다. 또한, 미로에는 몬스터가 배치되며 밤이 되면 위협을 가한다.

 

미로는 2차원 정수 배열 maze 로 주어지며, 이 미로의 각 위치는 다음 중 한가지로 주어진다.

• 0 : 이동할 수 있는 일반 길
• 1 : 이동할 수 없는 벽
• 2 : 밤에 나타나 주변을 위협하는 몬스터

플레이너는 항상 좌측 상단인 (0, 0) 위치에서 시작하며, 도착지는 항상 가장 우측 하단이다.

플레이어는 한 턴에 상, 하, 좌, 우 중 하나를 선택하여 한 칸씩 이동할 수 있으며, 필요에 따라 한 턴 동안 제자리에 가만히 있을 수 도 있다. 단, 1로 표기된 벽으로는 이동할 수 없다.

 

게임이 시작될 때는 '낮' 상태에서 시작하며, 5턴마다 낮과 밤이 바뀐다. 즉, 첫 다섯 턴은 '낮' 상태이며, 다음 다섯 턴은 '밤', 그리고 또 다음 다섯 턴은 '낮', ... 으로 반복된다.

 

미로에 2로 표기되어 있는 몬스터는 밤에만 등장하며, 몬스터가 위치한 장소를 포함하여 몬스터의 상, 하, 좌, 우 총 5칸을 위협한다. 이 때 플레이어가 위협적인 장소에 위치한 상태라면 탈출에 실패하고 게임이 종료된다.

 

이 때, 도착점에 도달하는 데에 걸리는 최소의 턴 수를 출력하시오. 단, 탈출할 수 없는 경우 -1을 반환하시오.

 

 

🎈 입력 설명

• 3 < maze.length <= 1000
• 3 < maze[i].length <= 1000

 

🎈 출력 설명

도착점에 도달하는 데에 걸리는 최소의 턴 수를 정수로 반환

 

 

🎈 매개변수 형식

maze = {{0, 0, 0, 0, 0, 0},
        {0, 1, 1, 1, 1, 0},
        {0, 1, 0, 2, 0, 0},
        {1, 1, 0, 1, 0, 1},
        {0, 0, 0, 0, 1, 0},
        {1, 1, 1, 0, 2, 0}}

 

 

🎈 반환값 형식

22

 

🎈 예시 입출력 설명

 

 

🎈 코드 구현

BFS 문제의 변형입니다.
일반 BFS 미로찾기에, 낮/밤에는 지도가 달라지는 기믹을 적용합니다.
visited 외에 waited를 하나 더 만들어서, 가만히 기다리는 턴 수를 기록합니다.
가만히 기다리는 턴 수는 최대 9턴(낮+밤이 한바퀴 도는 동안)까지만 기다려보면 되기 때문입니다.
새로운 곳에 도달하면, 상하좌우 이동하는 것 외에 1~9턴 대기하고 출발하는 것도 같이 시도해 보는 것이지요!
또한 지도를 하나 더 만들어, 밤에는 밤 지도를 참고합니다.

 

참고하면 좋을 개념

https://smarthammer.tistory.com/121

 

import java.util.LinkedList;
import java.util.Queue;

class Solution {
    public int solution(int[][] maze) {
        int N = maze.length;
        int M = maze[0].length;

        Queue<int[]> q = new LinkedList<>();
        q.offer(new int[]{0, 0, 0}); // i=0, j=0, turn=0

        // 상, 하, 좌, 우, 가만히
        int[] diArray = {-1, 1, 0, 0, 0};
        int[] djArray = {0, 0, -1, 1, 0};

        // 방문 여부 & 소요 턴 수
        int[][] visited = new int[N][M];

        // 대기 턴 수 (최대 9회)
        int[][] waited = new int[N][M];

        // 밤 전용 미로판 생성
        int[][] mazeNight = new int[N][M];
        for (int i = 0; i < N; i++) {
            System.arraycopy(maze[i], 0, mazeNight[i], 0, M);
        }

        // 밤 전용 미로판은 몬스터와 위협 장소를 3으로 표기한다.
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (maze[i][j] == 2) {  // 몬스터가 위치하고 있는 곳
                    mazeNight[i][j] = 3;
                } else if (i > 0 && maze[i - 1][j] == 2) {  // 몬스터 위치의 아래쪽(하) 값 변경
                    mazeNight[i][j] = 3;
                } else if (i < N - 1 && maze[i + 1][j] == 2) { // 몬스터 위치의 위쪽(상) 값 변경
                    mazeNight[i][j] = 3;
                } else if (j > 0 && maze[i][j - 1] == 2) { //몬스터 위치의 왼쪽(좌) 값 변경
                    mazeNight[i][j] = 3;
                } else if (j < M - 1 && maze[i][j + 1] == 2) { //몬스터 위치의 오른쪽(우) 값 변경
                    mazeNight[i][j] = 3;
                }
            }
        }

        int[][][] mazes = {maze, mazeNight};

        // BFS 구현
        while (!q.isEmpty()) {
            int[] init = q.poll();
            int i = init[0];
            int j = init[1];
            int turn = init[2];
            int date = (turn / 5) % 2; // 0 : 낮, 1 : 밤

            if (mazes[date][i][j] == 3) {
                continue;
            }

            // 도착지점에 도착했을 때
            if (i == N - 1 && j == M - 1) {
                return visited[i][j];
            }

            for (int k = 0; k < diArray.length; k++) {
                int newI = i + diArray[i];
                int newJ = j + djArray[i];

                //제자리에서 기다리는 경우
                if (newI == i && newJ == j) {

                    // 밤 + 낮 한바퀴 기다렸으면 더 기다리지 않음
                    if (waited[newI][newJ] >= 10) {
                        continue;
                    }

                    // 기다리는 경우 추가
                    q.add(new int[]{newI, newJ, turn + 1});
                    waited[newI][newJ]++;
                    visited[newI][newJ]++;
                }

                // 이동한 좌표 위치가 미로 범위를 벗어났을 때
                if (newI < 0 || newI >= N || newJ < 0 || newJ >= M) {
                    continue;
                }

                // 이미 방문했던 길일 때
                if (visited[newI][newJ] > 0) {
                    continue;
                }

                // 다음 턴에 길이거나 비활성화 몬스터면 이동 가능
                int nextDate = ((turn + 1) / 5) % 2;
                if(mazes[nextDate][newI][newJ] == 0 || mazes[nextDate][newI][newJ] ==2) {
                    q.offer(new int[] {newI, newJ, turn + 1});
                    visited[newI][newJ] = visited[i][j] + 1;
                }
            }
        }
        return -1;
    }
}