프로그래머스 Level 2 – 게임 맵 최단거리(Java, BFS)

🎮 프로그래머스 Level 2 – 게임 맵 최단거리(Java, BFS)

이번에 풀어본 문제는 프로그래머스에서 BFS 대표 문제로 유명한
**“게임 맵 최단거리”**다.

시작점(0,0)에서 도착점(n-1,m-1)까지 최소 몇 번 만에 갈 수 있는지를 구하는 문제이며,
정답은 BFS로 간단하게 해결할 수 있다.

---

📌 문제 요약

• maps[i][j] == 1 → 이동 가능
• maps[i][j] == 0 → 벽이라 이동 불가
• (0,0)에서 출발해 (n-1,m-1)까지 가는 데 필요한 최소 이동 거리를 반환
• 갈 수 없다면 -1 반환

즉, 미로 최단거리 문제이므로 BFS가 정석이다.

---

🧠 핵심 아이디어

✔ 1. BFS는 최단거리 찾기에 최적화된 알고리즘

한 번 방문한 칸은 그때의 이동 거리가 최단 거리다.

✔ 2. maps 배열을 그대로 ‘거리 저장 용도’로 활용

• 처음 1이었던 칸을
  이전 칸까지의 이동 거리 + 현재 칸(1)
  으로 업데이트
• 별도의 dist 배열이 필요 없다.

✔ 3. 이웃한 칸이 1일 때만 이동

벽(0)은 건너뛴다.

---

🧩 자바 코드 (BFS)

 

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[]> q = new ArrayDeque<>();
        q.add(new int[]{0, 0});
        
        while(!q.isEmpty()){
            int[] cur = q.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 || nx >= n || ny < 0 || ny >= m) continue;
                if(maps[nx][ny] == 0 || maps[nx][ny] != 1) continue;
                
                q.add(new int[]{nx, ny});
                maps[nx][ny] = maps[x][y] + maps[nx][ny];
            }
        }
        
        if(maps[n-1][m-1] == 1){
            return -1;
        } else {
            return maps[n-1][m-1];
        }
    }
}

---

🔍 코드 설명

✔ Queue로 BFS 시작

(0,0)을 넣고 시작한다.

✔ maps 값을 이용해 거리 업데이트

maps[nx][ny] = maps[x][y] + 1 과 동일한 의미
처음 maps[x][y]가 1이므로 실제 거리 값이 저장됨.

✔ visited 배열 없이도 OK

맵에서 1이 아닌 값은 이미 방문한 곳이므로 불필요.

✔ 마지막 칸이 여전히 1이라면 도달 불가

그래서 maps[n-1][m-1] == 1인 경우 → -1 반환.

---

📘 시간 복잡도

• BFS 전체 탐색: O(n × m)
• 지도 최대 크기가 크지 않아 충분히 빠르다.

---

🎯 최종 정리

이 문제는 BFS의 기본기를 다지기에 정말 좋은 문제다.
특히 맵 배열 자체를 거리 배열로 바꾸는 방식이 아주 깔끔하고 실용적이다.