[Java] 게임 맵 최단거리

나의 풀이(정답코드) + 주석

import java.util.*;

class Solution {
    // 기본 setting 값
    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 탐색을 위한 큐
        
        // BFS 탐색 시작점 추가 : (0,0)과 거리를 큐에 추가
        queue.add(new int[] {0,0,1}); // (n, m, dis)
        visited[0][0] = true; // 시작위치 : 방문으로 표시
        // 4방향 배열, 상하좌우
        int[] dr = {0,1,0,-1}; // 열
        int[] dc = {-1,0,1,0}; // 행
        
        // 큐가 비어있지 않은 동안 BFS 탐색
        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;
            }
            
            // 5*5(n*m) 범위 내에서 이동할 때
            for(int d = 0; d<4; d++) {
                // 다음 위치 계산, 현재 + 다른방향 거리
                int nr = r+dr[d], nc=c+dc[d];
                // n과 m은 0부터 n,m까지 이동 가능, 상하좌우 중 1칸씩만 이동
                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});
                    }
                    
                }
            }
        }
        return -1;
    }
}

오답노트

• import java.util.*; 추가하기 : Queue와 ArrayDeque를 불러오기 위한 용도
• 변수 이름 오타
  • 오답 : mmpas[nr][nc] == 1
  • 수정된 코드 : maps[nr][nc] == 1
• 변수 'i' 사용의 오류
  • 오답 : int r = cur[0], c = cur[i], dist = cur[2];
  • 수정된 코드 : int r = cur[0], c = cur[1], dist = cur[2]
• int r = cur[0], c = cur[i], dist = cur[2];
• 배열 초기화 설정 오류(괄호 문제)
  • 오답 : queue.add(new int);
  • 수정된 코드 : queue.add(new int[]{0, 0, 1});

해설집

import java.util.*;

class Solution {
    public int solution(int[][] maps) {
        int n = maps.length;  // 맵의 행(row) 개수
        int m = maps[0].length;  // 맵의 열(column) 개수
        boolean[][] visited = new boolean[n][m];  // 각 위치의 방문 여부를 저장하는 배열
        Queue<int[]> queue = new ArrayDeque<>();  // BFS 탐색을 위한 큐

        // BFS 탐색 시작점 추가: 시작 위치 (0, 0)과 거리를 큐에 추가
        queue.add(new int[]{ 0, 0, 1 });
        visited[0][0] = true;  // 시작 위치를 방문으로 표시
        
        // 상, 하, 좌, 우 방향을 나타내는 배열
        int[] dr = { 0, 1, 0, -1 };  // 행(row) 방향 이동: 좌, 하, 우, 상
        int[] dc = { -1, 0, 1, 0 };  // 열(column) 방향 이동: 좌, 하, 우, 상
        
        // 큐가 비어 있지 않은 동안 BFS 탐색을 수행
        while (!queue.isEmpty()) {
            int[] cur = queue.remove();  // 큐의 앞에서 현재 위치와 거리를 가져옴
            int r = cur[0], c = cur[1], dist = cur[2];  // 현재 행(r), 열(c), 거리(dist) 저장
            
            // 목적지 도달 시 현재 거리를 반환
            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];  // 다음 위치 계산
                
                // 맵의 범위를 벗어나지 않고, 이동 가능한 곳(1)이며, 아직 방문하지 않은 위치라면
                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;
    }
}

상세 설명

1. 맵 크기 설정:

   • n과 m 변수에 각각 맵의 행(row)과 열(column) 개수를 저장합니다.

2. 방문 여부 배열 초기화:

   • visited 배열을 사용해 각 위치의 방문 여부를 추적합니다. 초기에는 모든 위치를 방문하지 않은 상태로 설정합니다.

3. BFS를 위한 큐 초기화:

   • queue는 BFS 탐색을 위해 사용되는 큐입니다. 시작 위치 (0, 0)와 시작 거리를 큐에 추가하고, 시작 위치를 방문으로 표시합니다.

4. 이동 방향 설정:

   • dr과 dc 배열을 사용해 상, 하, 좌, 우 방향으로 이동을 나타냅니다.

5. BFS 탐색:

   • 큐가 비어있지 않은 동안 계속 탐색을 진행합니다. 큐의 앞에서 현재 위치와 거리를 가져오고, 현재 위치가 목적지인지 확인합니다.
   • 현재 위치가 목적지 (n-1, m-1)라면 현재 거리를 반환합니다.
   • 상, 하, 좌, 우 방향으로 이동을 시도합니다. 이동 가능한 위치인지 확인하고, 이동 가능하며 아직 방문하지 않은 위치라면 그 위치를 큐에 추가하고 방문으로 표시합니다.

6. 탐색 종료:

   • 모든 탐색을 마친 후에도 목적지에 도달하지 못했다면 -1을 반환합니다. 이는 목적지에 도달할 수 없는 경우를 의미합니다.

이 BFS 알고리즘은 최단 경로를 찾는 데 적합하며, 맵의 각 위치를 한 번씩만 방문하기 때문에 효율적입니다.