[프로그래머스|JAVA] 게임 맵 최단거리 | ↔️ BFS 활용 | Queue 활용

[문제 링크]

프로그래머스

 

[문제]

 

 

---

 

📍 [코드]

import java.util.*;

class Solution {
    public int solution(int[][] maps) {
        int n = maps.length;       // 행
        int m = maps[0].length;    // 열
        
        // 방향 배열 (상, 하, 좌, 우)
        int[] dx = {0, 0, -1, 1};
        int[] dy = {-1, 1, 0, 0};
        
        Queue<int[]> queue = new LinkedList<>();
        queue.offer(new int[]{0, 0}); // 시작점
       
        while (!queue.isEmpty()) {
            int[] cur = queue.poll();
            int x = cur[0];
            int y = cur[1];
            
            // 네 방향 탐색
            for (int i = 0; i < 4; i++) {
                int nx = x + dx[i];
                int ny = y + dy[i];
                
                // 범위 밖이면 패스
                if (nx < 0 || ny < 0 || nx >= n || ny >= m) continue;
                // 벽이거나 이미 방문한 곳이면 패스
                if (maps[nx][ny] != 1) continue;
                
                // 거리 갱신 = 현재 위치 + 1
                maps[nx][ny] = maps[x][y] + 1;
                queue.offer(new int[]{nx, ny});
            }
        }
        
        // 도착점에 저장된 값이 최단거리
        return maps[n-1][m-1] == 1 ? -1 : maps[n-1][m-1];
    }
}

 

💡 접근법

• 큐를 활용하여 탐색할 위치가 남아있는 동안 반복
• 시작점 (0,0)을 기준으로 네 방향을 탐색하며
  • 범위 밖이거나 방문한 곳이면 continue를 주어 무시함
  • 범위 내에 방문하지 않은 곳이라면 지금까지 걸린 거리를 저장하고
  • 처음 maps[0][0] = 1→ 이후 계속 누적
• 최종적으로 maps[n-1][m-1]에 최단 거리가 저장됨
  • 여전히 1이면 방문 못했다는 뜻 → 1

 

✅ 최단거리를 구하는 문제이므로 BFS 활용

✅ BFS 이므로 Queue 활용

 

 

---

 

💬 마무리

아직도 BFS / DFS 문제는 낯설고 어려운 것 같다... 온전히 혼자만의 힘으로 구현해내고 싶은데 아쉽다.
최단거리 = BFS = Queue 까지는 이제 알겠다.