[프로그래머스] 게임 맵 최단거리

코드 힌트

1. BFS (너비 우선 탐색) 사용하기
   • 최단 거리를 찾는 문제에서는 BFS를 사용하는 것이 효율적입니다. BFS는 시작점에서 모든 노드를 레벨별로 탐색하며, 가장 먼저 도달한 경로가 최단 경로가 됩니다. DFS를 사용할 경우, 모든 경로를 탐색해야 하므로 효율성 문제로 인해 시간 초과가 발생할 수 있습니다.
2. Queue 자료구조 활용
   • BFS를 구현할 때는 Queue를 사용합니다. Queue는 FIFO(First-In-First-Out) 구조를 가지며, 탐색할 좌표와 현재까지의 거리를 저장하는 데 유용합니다. Queue를 통해 현재 위치에서 가능한 모든 이동을 처리하고, 다음 단계의 위치와 거리 정보를 큐에 추가합니다.
3. 좌표와 거리 저장
   • 탐색 과정에서 각 좌표와 해당 좌표까지의 거리 정보를 함께 저장합니다. 이를 통해 이동할 수 있는 경로를 탐색하고, 새로운 좌표와 그에 대한 거리 정보를 큐에 추가할 수 있습니다.
   • 분기별로 좌표와 거리를 저장하면, 경로가 나누어졌을 때 각각의 경로를 독립적으로 처리할 수 있습니다.
4. 도착 실패 시 처리
   • 도착점 (n-1, m-1)에 도달하지 못한 경우, 최단 거리를 찾지 못한 것이므로 -1을 반환해야 합니다. BFS 탐색이 완료된 후에도 도착하지 못한 경우를 체크하여, -1을 반환함으로써 실패를 명확히 할 수 있습니다.

 

---

정답은 더보기 클릭

import java.util.*;

class Solution {
    
    // 맵의 크기
    static int n, m;
    
    // 최단 거리 결과를 저장하는 변수 (초기값: Integer.MAX_VALUE, 도착하지 못한 경우 -1로 설정)
    static int result = Integer.MAX_VALUE;
    
    // 방문 여부를 체크하는 배열
    static boolean[][] visited;
    
    // 상하좌우 이동을 위한 방향 배열
    static final int[] dx = {1, 0, -1, 0};
    static final int[] dy = {0, 1, 0, -1};
    
    public int solution(int[][] maps) {
        // 맵의 크기 초기화
        n = maps.length;
        m = maps[0].length;
        
        // 방문 여부 배열 초기화
        visited = new boolean[n][m];
        
        // BFS 메서드 실행
        bfs(maps);
        
        // 도착하지 못한 경우 -1 반환
        if (result == Integer.MAX_VALUE) {
            return -1;
        }
        
        // 최단 거리 반환
        return result;
    }
    
    // 너비 우선 탐색 (BFS) 메서드
    static void bfs(int[][] maps) {
        // 큐 생성: 좌표 (x, y)와 이동 거리를 저장
        Queue<int[]> queue = new LinkedList<>();
        
        // 시작점 (0, 0)과 거리 1을 큐에 추가
        queue.add(new int[]{0, 0, 1});
        visited[0][0] = true;
        
        // 큐가 비어 있을 때까지 반복
        while (!queue.isEmpty()) {
            // 큐에서 현재 위치와 거리 추출
            int[] currentPosition = queue.poll();
            int x = currentPosition[0];
            int y = currentPosition[1];
            int distance = currentPosition[2];
            
            // 상하좌우 4가지 방향으로 이동
            for (int i = 0; i < 4; i++) {
                int nextX = x + dx[i];
                int nextY = y + dy[i];
                
                // 맵의 범위를 벗어나지 않고, 방문하지 않은 위치이며, 값이 1인 경우
                if (nextX >= 0 && nextY >= 0 && nextX < n && nextY < m &&
                   !visited[nextX][nextY] && maps[nextX][nextY] == 1) {
                    // 다음 위치와 거리 +1을 큐에 추가하고, 방문 표시
                    visited[nextX][nextY] = true;
                    queue.add(new int[]{nextX, nextY, distance + 1});
                    
                    // 도착점 (n-1, m-1)에 도달했을 경우 최단 거리 업데이트
                    if (nextX == n - 1 && nextY == m - 1) {
                        result = Math.min(result, distance + 1);
                    }
                }
            }
        }
    }
}

 

주석 제거

import java.util.*;

class Solution {
    
    static int n, m;
    
    static int result = Integer.MAX_VALUE;
    
    static boolean[][] visited;
    
    static final int[] dx = {1, 0, -1, 0};
    static final int[] dy = {0, 1, 0, -1};
    
    public int solution(int[][] maps) {
        n = maps.length;
        m = maps[0].length;
        
        visited = new boolean[n][m];
        
        bfs(maps);
        
        if (result == Integer.MAX_VALUE) {
            return -1;
        }
        
        return result;
    }
    
    static void bfs(int[][] maps) {
        Queue<int[]> queue = new LinkedList<>();
        
        queue.add(new int[]{0, 0, 1});
        visited[0][0] = true;
        
        while (!queue.isEmpty()) {
            int[] currentPosition = queue.poll();
            int x = currentPosition[0];
            int y = currentPosition[1];
            int distance = currentPosition[2];
            
            for (int i = 0; i < 4; i++) {
                int nextX = x + dx[i];
                int nextY = y + dy[i];
                
                if (nextX >= 0 && nextY >= 0 && nextX < n && nextY < m &&
                   !visited[nextX][nextY] && maps[nextX][nextY] == 1) {
                    visited[nextX][nextY] = true;
                    queue.add(new int[]{nextX, nextY, distance + 1});
                    
                    if (nextX == n - 1 && nextY == m - 1) {
                        result = Math.min(result, distance + 1);
                    }
                }
            }
        }
    }
}