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

문제 링크

---

1. 아이디어

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

거리는 dist 배열을 활용했으며 시작 칸부터 거리 1로 세므로 0으로 초기화한 후 0이면 방문하지 않은 칸으로 판정했다.

---

2. 복잡도

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

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

---

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();
            int r = cur[0];
            int 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;

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

        return -1;
    }
}

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

const int MAX_N = 100;
int dist[MAX_N][MAX_N];
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])

    q = deque([(0, 0)])
    dist = [[0] * m for _ in range(n)]
    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

---