[Java] 미로 탈출

1. 문제

지도는 세로가 N, 가로가 M인 2차원 정수 배열 maze 로 주어져 있으며, 현재 위치는 (0, 0)이고 출구의 위치는 (N-1, M-1) 이다.

지도에는 갈 수 있는 위치는 0 으로, 갈 수 없는 위치는 1 로 표기되어 있다.

이 때, 미로를 가장 빠르게 탈출할 경우의 이동 횟수를 출력하시오.

단, 미로를 탈출할 수 없는 경우에는 -1을 출력하시오.

 

 

2. 입력 설명

• 0 < N <= 1000
• 0 < M <= 1000

 

3. 출력 설명

미로를 탈출하는 데에 필요한 최소 이동 횟수를 정수로 출력

 

 

4. 매개변수 형식

N = 6

M = 6

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

 

 

 

 

5. 반환값 형식

16

 

 

6. 코드 구현

힌트 : BFS

 

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

class Solution {

    public int solution(int N, int M, int[][] maze) {

        // BFS 이므로 Queue 사용
        Queue<int[]> q = new LinkedList<>();

        // 현재 위치
        q.offer(new int[]{0, 0});

        int[] xArray = {0, 0, 1, -1};
        int[] yArray = {1, -1, 0, 0};

        // 방문여부 및 방문 횟수 저장
        // 만약 0이라면 방문한 적 X
        int[][] visited = new int[N][M];

        while (!q.isEmpty()) {
            int[] currentLocation = q.poll();
            int x = currentLocation[0];
            int y = currentLocation[1];

            // 도착지점에 도착하면 방문횟수 바로 반환
            if (x == N - 1 && y == M - 1) {
                return visited[x][y];
            }

            for (int i = 0; i < 4; i++) {
                int newX = x + xArray[i];
                int newY = y + yArray[i];

                // 새로운 좌표가 미로 바깥에 위치할 때
                if (newX < 0 || newX >= N || newY < 0 || newY >= M) {
                    continue;
                }

                // 새로운 좌표가 갈 수 있는 위치이고,
                // 방문한 적이 없는 경우
                if (maze[newX][newY] == 0 && visited[newX][newY] == 0) {
                    q.offer(new int[]{newX, newY});
                    visited[newX][newY] = visited[x][y] + 1;
                }
            }
        }
        return -1;
    }
}