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

• 프로그래머스 문제 URL

---

문제 요약

maps는 2차원 격자(게임 맵)이고, 1은 이동 가능, 0은 벽(이동 불가)이다.
시작점 (0,0)에서 도착점 (n-1,m-1)까지 최단거리(최소 칸 수) 로 이동할 때의 거리를 구하는 문제다.
도착할 수 없으면 -1을 반환한다.

---

핵심 아이디어

이 문제는 “상/하/좌/우로 한 칸 이동 = 비용이 항상 1”인 최단거리 문제라서 BFS가 정답이다.
BFS는 거리(레벨) 순서대로 확장하므로, 도착 지점에 처음 도달했을 때의 거리가 곧 최단거리다.

---

상태 설계(큐에 뭘 넣을까?)

이 코드는 큐에 다음 3가지를 같이 저장한다.

• x, y : 현재 좌표
• r : 시작점에서 현재 칸까지의 거리(지나온 칸 수)

Queue<int[]> queue = new LinkedList<>();
queue.add(new int[]{0, 0, 1}); // 시작 칸도 거리 1로 포함

거리 배열(dist[][])을 따로 두지 않고, 큐에 거리까지 들고 다니는 방식이라 구현이 직관적이다.

---

visited 처리가 핵심인 이유

2차원 격자 BFS에서 visited가 없으면 같은 칸이 여러 경로로 계속 큐에 들어가면서 탐색량이 급증한다.
그래서 “큐에 넣는 순간” 방문 처리로 중복 삽입을 차단한다.

visited = new boolean[maps.length][maps[0].length];
visited[0][0] = true;

그리고 다음 칸으로 갈 때도:

if (maps[nx][ny] == 1 && !visited[nx][ny]) {
    visited[nx][ny] = true;
    queue.add(new int[]{nx, ny, r + 1});
}

이렇게 해야 BFS의 “최초 방문이 최단거리” 성질이 깔끔하게 유지된다.

---

4방향 이동(dy/dx) 패턴

상하좌우 이동은 dx/dy 배열로 관리하면 코드가 단순해진다.

int[] dx = {1, -1, 0, 0};
int[] dy = {0, 0, 1, -1};

그리고 다음 좌표 (nx, ny)가 맵 범위 안인지 체크한 뒤 진행한다.

if (nx >= 0 && nx < maps.length && ny >= 0 && ny < maps[0].length) {
    ...
}

---

도착 시점에 바로 종료하는 이유

너 코드는 도착점을 큐에 넣는 순간 바로 종료한다.

if (nx == maps.length - 1 && ny == maps[0].length - 1) {
    answer = r + 1;
    break loop1;
}

BFS는 거리가 증가하는 순서대로 진행하니까, 도착점을 “처음 발견한 순간”의 r+1이 최단거리여서 이렇게 바로 끊어도 안전하다.
(반대로 DFS는 이런 식으로 끊으면 최단거리를 보장할 수 없음)

---

전체 코드(제출용)

import java.util.LinkedList;
import java.util.Queue;

class Solution {
    static boolean[][] visited;

    public int solution(int[][] maps) {
        int answer = -1;

        Queue<int[]> queue = new LinkedList<>();
        queue.add(new int[]{0, 0, 1}); // {x, y, dist}

        visited = new boolean[maps.length][maps[0].length];
        visited[0][0] = true;

        int[] dx = {1, -1, 0, 0};
        int[] dy = {0, 0, 1, -1};

        loop1:
        while (!queue.isEmpty()) {
            int[] temp = queue.poll();
            int x = temp[0];
            int y = temp[1];
            int r = temp[2];

            for (int i = 0; i < 4; i++) {
                int nx = dx[i] + x;
                int ny = dy[i] + y;

                if (nx >= 0 && nx < maps.length && ny >= 0 && ny < maps[0].length) {
                    if (maps[nx][ny] == 1 && !visited[nx][ny]) {
                        visited[nx][ny] = true;
                        queue.add(new int[]{nx, ny, r + 1});

                        if (nx == maps.length - 1 && ny == maps[0].length - 1) {
                            answer = r + 1;
                            break loop1;
                        }
                    }
                }
            }
        }

        return answer;
    }
}