[Java] 게임 맵 최단거리

게임 맵 최단거리

접근 방법

• N,M 이 100 이하이고 최단 거리를 구하는 문제이므로 BFS 를 이용해야겠다고 생각

문제 풀이

import java.util.*;

class Solution {
    public int solution(int[][] maps) {
        int n = maps.length;
        int m = maps[0].length;
        boolean[][] visited = new boolean[n][m];
        Queue<int[]> queue = new ArrayDeque<>();

        //✅ BFS 탐색을 수행한다.
        queue.add(new int[]{ 0, 0, 1 });
        visited[0][0] = true;
        
        int[] dr = { 0, 1, 0, -1 };
        int[] dc = { -1, 0, 1, 0 };
        
        while (!queue.isEmpty()) {
            int[] cur = queue.remove();
            int r = cur[0], c = cur[1], dist = cur[2];
            
            //✅ 탐색 과정에서 목적지에 도달하면 거리를 반환한다.
            if (r == n - 1 && c == m - 1) {
                return dist;
            }

            for (int d = 0; d < 4; d++) {
                int nr = r + dr[d], nc = c + dc[d];
                
                if (nr >= 0 && nr < n && nc >= 0 && nc < m && maps[nr][nc] == 1) {
                    if (!visited[nr][nc]) {
                        visited[nr][nc] = true;
                        queue.add(new int[]{ nr, nc, dist + 1 });
                    }
                }
            }
        }
        //✅ 탐색 과정에서 목적지에 도달하지 못했다면 -1을 반환한다.
        return -1;
    }
}

배우게 된 점

• (BFS 알고리즘) 큐에 새 위치 추가하기 전 이동이 가능한지 확인하는 법
  

    // 이 조건문은 BFS(너비 우선 탐색) 알고리즘에서 큐에 새 위치를 추가하기 전에 그 위치가 유효한지, 
    // 즉, 이동이 가능한지를 확인하는 역할
    
    if (0 <= nr && nr < rowLengh && 0 <= nc && nc < colLength && maps[nr][nc] == 1) {
    }

- **`0 <= nr && nr < rowLengh`**:
    - **설명**: `nr`은 새로운 행의 인덱스를 나타냅니다. 이 조건은 `nr`이 유효한 행 인덱스인지 확인합니다. 즉, `nr`이 0 이상이고 `rowLengh` (전체 행의 수)보다 작아야 한다는 것입니다. 이렇게 함으로써 `nr`이 배열의 유효 범위 내에 있는지 검토합니다.
- **`0 <= nc && nc < colLength`**:
    - **설명**: `nc`는 새로운 열의 인덱스를 나타냅니다. 이 조건은 `nc`가 유효한 열 인덱스인지 확인합니다. 즉, `nc`가 0 이상이고 `colLength` (전체 열의 수)보다 작아야 한다는 것입니다. 이렇게 함으로써 `nc`가 배열의 유효 범위 내에 있는지 검토합니다.
- **`maps[nr][nc] == 1`**:
    - **설명**: `maps[nr][nc]`는 새로운 위치의 값입니다. 이 조건은 새로운 위치가 이동 가능한 경로인지 확인합니다. `maps[nr][nc]`가 1이면 해당 위치가 이동 가능한 경로임을 의미합니다. 0이라면 벽이나 장애물이 있을 수 있으며, 이동할 수 없는 위치로 간주됩니다.