munjjang9
문짱구의 게임 개발 블로그
Game Programmer

[프로그래머스] 게임 맵 최단거리 (Lv.2)

•

문제 링크

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


문제 설명

ROR 게임에서 당신은 상대 팀 진영을 공격하기 위해 지금 제일 빠른 길을 찾아야 합니다.

지도는 n×m 크기의 2차원 배열입니다. 0은 벽으로 막힌 공간, 1은 이동할 수 있는 공간입니다. 캐릭터는 좌, 우, 위, 아래 네 방향으로만 이동할 수 있습니다.

캐릭터가 처음 놓인 칸 (1, 1)에서 상대 팀 진영인 (n, m)까지 최단거리로 이동하면 몇 칸을 지나야 하는지 구해주세요. 이동할 수 없는 경우 -1을 반환합니다.

제한사항

  • maps는 n × m 크기의 게임 맵의 상태가 들어있는 2차원 배열로, n과 m은 각각 1 이상 100 이하의 자연수입니다.
  • n과 m은 서로 같을 수도, 다를 수도 있지만, n과 m이 모두 1인 경우는 입력으로 주어지지 않습니다.
  • maps는 0과 1로만 이루어져 있으며, 0은 벽이 있는 자리, 1은 벽이 없는 자리를 나타냅니다.
  • 처음에 캐릭터는 게임 맵의 좌측 상단인 (1, 1) 위치에 있으며, 상대방 진영은 게임 맵의 우측 하단인 (n, m) 위치에 있습니다.


내 풀이

2D 격자를 그래프로 보고 BFS로 최단거리를 탐색했다.

dist 배열을 -1로 초기화해 미방문 표시와 visited 역할을 겸하게 했다. 시작점 (0, 0)에서 출발해 상하좌우 4방향으로 이동하며, 이동할 때마다 dist[nx][ny] = dist[x][y] + 1로 거리를 누적한다. 목적지 (N-1, M-1)에 도달하면 dist[x][y] + 1을 반환하고, 큐가 빌 때까지 도달하지 못하면 -1을 반환한다.

#include <vector>
#include <queue>
using namespace std;

int N = 0, M = 0;
vector<vector<int>> Maps;

int Dx[] = { 0,  0, +1, -1};
int Dy[] = {+1, -1,  0,  0};

int bfs(int start_x, int start_y)
{
    queue<pair<int, int>> q;
    vector<vector<int>> dist(N, vector<int>(M, -1));
    
    q.push({start_x, start_y});
    dist[start_x][start_y] = 0;
    
    while(!q.empty())
    {
        auto [x, y] = q.front();
        q.pop();
        
        if(x == N-1 && y == M-1) return dist[x][y] + 1;
        
        for(int d = 0; d < 4; d++)
        {
            int nx = x + Dx[d];
            int ny = y + Dy[d];
            
            if(nx < 0 || nx >= N || ny < 0 || ny >= M) continue;
            
            if(Maps[nx][ny] == 0) continue;
            if(dist[nx][ny] != -1) continue;
            
            dist[nx][ny] = dist[x][y] + 1;
            q.push({nx, ny});
        }
    }
    
    return -1;
}


int solution(vector<vector<int> > maps)
{
    Maps = maps;
    N = (int)maps.size();
    M = (int)maps[0].size();
    
    return bfs(0,0);
}


시간복잡도 분석

N×M 격자의 모든 칸을 최대 한 번씩만 방문하므로 전체 시간복잡도는 O(N × M)이다.

단계 시간복잡도
BFS 전체 탐색 O(N × M)

제한사항에서 N, M ≤ 100이므로 최대 10,000 연산으로 충분히 통과 가능하다.


오답노트

오류: 이동 횟수와 칸의 수 혼동

// 수정 전
if(x == N-1 && y == M-1) return dist[x][y];    // 이동 횟수(엣지 수) 반환

// 수정 후
if(x == N-1 && y == M-1) return dist[x][y] + 1; // 칸의 수(노드 수) 반환

dist[0][0] = 0으로 시작하면 목적지의 dist 값은 이동 횟수(엣지 수)다. 문제가 요구하는 건 “몇 칸을 지나야 하는지” — 시작 칸을 포함한 칸의 수(노드 수)이므로 +1이 필요하다.

(0,0) → (1,0) → ... → (N-1,M-1)
dist:  0      1           10      → 반환값: 10 + 1 = 11칸


후기

이 문제도 어떻게 풀어야 하는지를 잘 몰라서 처음에 많이 헤매다가 공부를 다시 하고 풀어봤다. 이렇게 푸는거구나 라는 흐름을 익히고 나중에 한 번 더 도전해보는 것도 좋을 것 같다.

Table of Contents