[Nossi] 응급차 최단 거리2

개발남노씨 강사님의 수업을 듣고 있어서 예제 문제로 노씨데브에 있는 문제도 가끔 공유해주신다.
이번에는 암시적 그래프의 가장 기초적인 문제인 응급차 최단거리를 가져왔다.

 

코딩테스트 문제 응급차 최단 거리2 - Nossi.Dev

 

---

문제 파악

문제 설명

한 도시에 큰 사고가 발생하여 응급차가 부상자를 구조하기 위해 출동해야 합니다. 도시는 m x n크기의 이진 행렬로 표현되며, 0은 차량이 통행 가능한 도로를, 1은 통행이 불가능한 구역을 나타냅니다. 응급차는 도시의 왼쪽 위(0, 0)에서 출발하여 오른쪽 아래(m-1, n-1)에 위치한 부상자를 구조해야 합니다.

응급차는 이동 가능한 도로(0)만을 따라 상하좌우 또는 대각선으로 인접한 칸으로 이동할 수 있으며, 경로의 길이는 방문한 칸의 개수로 정의됩니다. 만약 응급차가 부상자에게 도달할 수 없는 경우, -1을 반환해야 합니다. 도로망을 분석하여 응급차가 도착할 수 있는 가장 짧은 경로의 길이를 반환하는 solution 함수를 작성해주세요.

입출력 예시

예시 1)

입력 :

city = [
    [0, 0, 1, 0],
    [1, 0, 1, 0],
    [1, 0, 0, 0]
]

출력 : 4

설명 : (0, 0) -> (1, 1) -> (2, 2) -> (2, 3)

 

예시 2)

입력 :

city = [
    [0, 1, 0],
    [0, 1, 0],
    [0, 0, 0],
    [1, 1, 0],
    [0, 0, 0]
]

출력 : 5

설명 : (0, 0) -> (1, 0) -> (2, 1) -> (3, 2) -> (4, 2)

 

예시 3)

입력 :

city = [
    [0, 0, 0, 0],
    [1, 1, 1, 0],
    [1, 0, 0, 0],
    [1, 1, 1, 1]
]

출력 : -1

설명 : 도착점 (3,3)의 값이 1이기 때문에 방문할 수 없습니다.

 

제한 사항

• m == city.length
• n == city[i].length
• city은 m x n 크기의 2차원 리스트이며, 1 ≤ m, n ≤ 300입니다.
• city[i][j]는 0 또는 1로만 구성됩니다.

요약하면,
m x n 의 도로에서 통행이 가능하면 0, 불가능하면 1로 구성되어 있음

응급차의 시작 위치를 (0,0) 이라고 할 때, 환자의 위치 (m-1, n-1) 까지의 최단거리를 구하는 문제
시작과 도착점이 1이라면 -1을 반환한다.

---

접근 방법

최단거리이기 때문에 바로 BFS 탐색이란 것을 알 수 있다.

시작이 1이면 종료, 환자에게 갈 수 없으면 종료

0으로 되어있는 도로만 움직일 수 있고, 환자에게 도달하면 최단거리를 반환

---

코드 구현

import java.util.*;

class Solution {
    public int solution(int[][] city) {
        int answer = -1;
        int m = city.length;
        int n = city[0].length;

        Queue<int[]> queue = new ArrayDeque<>();

        int[] dr = {0, 1, 1, 1, 0, -1, -1, -1};
        int[] dc = {1, 1, 0, -1, -1, -1, 0, 1};

        boolean[][] visited = new boolean[m][n];

        // 시작점이 1이면 바로 종료
        if(city[0][0] == 1) return answer;

        // 거리를 큐에 같이 추가
        queue.offer(new int[]{0,0,1});

        // 방문 배열
        visited[0][0] = true;

        // 탐색
        while(!queue.isEmpty()){
            int[] cur = queue.poll();
            int r = cur[0];
            int c = cur[1];
            int dist = cur[2];

            // 환자에게 도달하면 거리 반환
            if(r == m-1 && c == n-1){
                return dist;
            }

            for(int i=0; i<8; i++){
                int nr = r + dr[i];
                int nc = c + dc[i];

                if(nr >= 0 && nr < m && nc >= 0 && nc < n){
                    if(!visited[nr][nc] && city[nr][nc] == 0){
                        queue.add(new int[]{nr, nc, dist + 1});
                        visited[nr][nc] = true;
                    }
                }
            }
        }
        return answer; // 찾을 수 없으면 -1 종료
    }
}