[Programmers] #1844 - 게임 맵 최단거리 [Java][C++][Python]

문제 링크

---

1. 아이디어

인접한 칸으로의 이동 비용이 모두 1이므로 최단 거리는 BFS로 구한다. 시작 칸 $(0, 0)$에서 큐를 초기화하고, 상하좌우 네 방향 중 맵 안이면서 벽이 아니고 아직 방문하지 않은 칸을 큐에 넣으며 거리를 하나씩 늘려 나간다.

dist 배열 하나로 방문 여부와 거리를 겸한다 — 값이 0이면 미방문이다. 문제는 출발 칸을 포함해 지나간 칸의 개수를 세므로 dist[0][0]을 1로 두고 시작한다. 도착 칸 $(N - 1, M - 1)$을 큐에서 꺼내는 순간의 dist 값이 답이며, 큐가 빌 때까지 도착하지 못하면 경로가 없다는 뜻이므로 -1을 반환한다.

---

2. 복잡도

접근	시간	공간
풀이	$O(N \times M)$	$O(N \times M)$

($N$ = maps의 행 수, $M$ = 열 수)

---

3. 코드

풀이 [Java][C++][Python]

import java.util.*;

class Solution {

    static int[] dr = {-1, 0, 1, 0};
    static int[] dc = {0, 1, 0, -1};

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

        Queue<int[]> q = new ArrayDeque<>();
        q.offer(new int[]{0, 0});

        int[][] dist = new int[n][m];
        dist[0][0] = 1;

        while (!q.isEmpty()) {
            int[] cur = q.poll();
            if (cur[0] == n - 1 && cur[1] == m - 1) return dist[cur[0]][cur[1]];

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

                if (nr < 0 || nr >= n || nc < 0 || nc >= m) continue;
                if (maps[nr][nc] == 0 || dist[nr][nc] != 0) continue;

                q.offer(new int[]{nr, nc});
                dist[nr][nc] = dist[cur[0]][cur[1]] + 1;
            }
        }

        return -1;
    }
}

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 100;
int dist[MAXN][MAXN];
int dr[4] = {-1, 0, 1, 0};
int dc[4] = {0, 1, 0, -1};

int solution(vector<vector<int>> maps) {
    int n = maps.size(), m = maps[0].size();

    queue<pair<int, int>> q;
    q.push({0, 0});
    dist[0][0] = 1;

    while (!q.empty()) {
        auto [r, c] = q.front();
        q.pop();

        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;

            q.push({nr, nc});
            dist[nr][nc] = dist[r][c] + 1;
        }
    }

    return -1;
}

from collections import deque


def solution(maps):
    n, m = len(maps), len(maps[0])
    dist = [[0] * m for _ in range(n)]

    q = deque([(0, 0)])
    dist[0][0] = 1

    while q:
        r, c = q.popleft()
        if (r, c) == (n - 1, m - 1):
            return dist[r][c]

        for dr, dc in ((-1, 0), (0, 1), (1, 0), (0, -1)):
            nr, nc = r + dr, c + dc

            if not (0 <= nr < n and 0 <= nc < m):
                continue
            if maps[nr][nc] == 0 or dist[nr][nc] != 0:
                continue

            q.append((nr, nc))
            dist[nr][nc] = dist[r][c] + 1

    return -1

---