[Java] 프로그래머스 - 게임 맵 최단거리 (BFS - 큐)

프로그래머스 1844 — 게임 맵 최단거리 (BFS)

📝 문제 설명

• 0과 1로 이루어진 2차원 맵이 주어진다.
• 시작 위치는 (0,0), 목표 위치는 (n-1,m-1)이다.
• 1은 이동 가능한 칸, 0은 벽이다.
• 이동은 상/하/좌/우 네 방향만 가능하다.
• 목표 위치까지 도달할 수 있는 최단 거리를 구한다.
• 만약 도달할 수 없다면 -1을 반환한다.

---

💡 풀이 아이디어

1. 최단 거리 문제 → BFS
   • DFS는 깊이 우선이라 최단 거리 보장 X
   • BFS는 레벨(거리) 단위로 탐색하기 때문에 첫 도착이 최단 거리
2. 거리 관리
   • dist[r][c] 배열을 두어 시작 칸은 1, 이후는 이전 칸 + 1로 기록
   • 방문 여부 체크도 dist를 통해 함께 처리
3. 큐에 좌표 저장
   • Queue<int[]>에 (r, c) 좌표를 넣고 꺼내며 탐색
   • new int[]{r, c} 형태로 배열에 담아 처리
4. 이동 방향
   • dr = {-1,1,0,0}, dc = {0,0,-1,1} → 상하좌우 이동 벡터

---

📌 코드 (Java)

import java.util.*;

class Solution {
// 상, 하, 좌, 우
static final int[] dr = {-1, 1, 0, 0};
static final int[] dc = {0, 0, -1, 1};

public int solution(int[][] maps) {
    int n = maps.length;
    int m = maps[0].length;

    int[][] dist = new int[n][m];           // 방문 + 거리 기록
    ArrayDeque<int[]> q = new ArrayDeque<>();

    // 시작점
    dist[0][0] = 1;
    q.offer(new int[]{0, 0});

    while (!q.isEmpty()) {
        int[] cur = q.poll();
        int r = cur[0], c = cur[1];

        // 목표 도착
        if (r == n - 1 && c == m - 1) return dist[r][c];

        for (int d = 0; d < 4; d++) {
            int nr = r + dr[d];
            int nc = c + dc[d];

            // 범위, 벽, 방문 체크
            if (nr < 0 || nr >= n || nc < 0 || nc >= m) continue;
            if (maps[nr][nc] == 0 || dist[nr][nc] != 0) continue;

            dist[nr][nc] = dist[r][c] + 1;
            q.offer(new int[]{nr, nc});
        }
    }
    return -1; // 도달 불가
}
}