프로그래머스 [연습문제 / 게임 맵 최단거리](C++) -yes6686- 티스토리

프로그래머스 문제 풀이: 1844 게임 맵 최단거리

---

문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/1844

문제 설명:

ROR 게임의 N×M 크기 맵에서 캐릭터가 (1,1) 위치에서 출발하여 상대 팀 진영인 (N,M) 위치까지 도달하는 최단 거리를 구하는 문제입니다. 맵은 1과 0으로 이루어져 있으며, 1은 벽이 없어 이동 가능한 곳이고, 0은 벽이 있어 이동할 수 없는 곳입니다. 한 칸씩 상하좌우로 이동할 수 있으며, 도달할 수 없으면 -1을 반환합니다.

---

문제 해결 코드

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

int solution(vector<vector<int>> maps) {
    int n = maps.size();        // 맵의 세로 크기
    int m = maps[0].size();     // 맵의 가로 크기
    
    // 방문 배열 초기화
    vector<vector<int>> visited(n, vector<int>(m, 0));
    
    // 4방향 이동 (상, 하, 좌, 우)
    int dx[4] = {-1, 1, 0, 0};
    int dy[4] = {0, 0, -1, 1};
    
    // BFS 탐색을 위한 큐
    queue<pair<int,int>> q;
    
    // 시작 지점 (0,0)에서 출발
    q.push({0, 0});
    visited[0][0] = 1;  // 시작 지점의 거리는 1
    
    while(!q.empty()) {
        int x = q.front().first;
        int y = q.front().second;
        q.pop();
        
        // 목적지에 도달하면 거리 반환
        if(x == n - 1 && y == m - 1) {
            return visited[x][y];
        }
        
        // 4방향 탐색
        for(int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            
            // 경계 체크
            if(nx < 0 || ny < 0 || nx >= n || ny >= m) continue;
            
            // 벽이거나 이미 방문한 곳은 제외
            if(maps[nx][ny] == 0 || visited[nx][ny]) continue;
            
            // 거리 갱신 및 큐에 추가
            visited[nx][ny] = visited[x][y] + 1;
            q.push({nx, ny});
        }
    }
    
    // 목적지에 도달할 수 없음
    return -1;
}

---

코드 설명

• 핵심 알고리즘: BFS(너비 우선 탐색)를 사용한 최단 경로 탐색입니다. BFS는 가중치가 없는 그래프에서 시작점부터 각 정점까지의 최단 거리를 보장합니다. 시작점 (0,0)에서 출발하여 목적지 (n-1, m-1)에 도달할 때까지 탐색하며, 각 칸에 도달하는 최소 거리를 visited 배열에 기록합니다.
• 구현 세부사항:
  • visited 배열을 vector로 선언하여 동적 크기 조정이 가능하도록 했습니다.
  • 시작 지점을 1로 초기화하여 거리를 추적합니다 (1부터 시작).
  • 목적지에 도달하면 즉시 거리를 반환하여 불필요한 탐색을 줄입니다.
  • maps[nx][ny] == 0 조건으로 벽을 체크합니다 (원본 코드는 반대로 변환했지만 불필요).
  • 전역 변수를 모두 제거하여 함수의 독립성을 높였습니다.
  • 큐가 비었는데 목적지에 도달하지 못하면 -1을 반환합니다.
• 시간/공간 복잡도: 시간 복잡도는 O(n ⋅ m)입니다. 최악의 경우 모든 칸을 한 번씩 방문하므로 맵의 크기에 비례합니다. 공간 복잡도는 O(n ⋅ m)으로 visited 배열과 큐에 사용되는 공간입니다. 큐는 최대 O(n ⋅ m) 크기까지 커질 수 있습니다.

---

실행 예시

입력:

maps = [[1,0,1,1,1],
        [1,0,1,0,1],
        [1,0,1,1,1],
        [1,1,1,0,1],
        [0,0,0,0,1]]

실행 과정:

• 맵 구조 (5×5):

  1 0 1 1 1
  1 0 1 0 1
  1 0 1 1 1
  1 1 1 0 1
  0 0 0 0 1

• 최단 경로 (visited 값):

  1  X  9  10 11
  2  X  8  X  12
  3  X  7  8  13
  4  5  6  X  14
  X  X  X  X  15

• 경로: (0,0) → (1,0) → (2,0) → (3,0) → (3,1) → (3,2) → (2,2) → (2,3) → (1,4) → (2,4) → (3,4) → (4,4)
• 총 거리: 11칸 이동

출력:

11

도달 불가능한 경우:

maps = [[1,0,1,1,1],
        [1,0,1,0,1],
        [1,0,1,1,1],
        [1,1,1,0,0],
        [0,0,0,0,1]]

우하단이 막혀 있어 (4,4)에 도달할 수 없으므로 -1을 반환합니다.

---

결과

BFS를 활용한 전형적인 최단 경로 문제입니다. 원본 코드의 전역 변수와 불필요한 배열 변환을 제거하여 코드를 간결하고 명확하게 개선했습니다. visited 배열을 vector로 선언하여 메모리 관리를 자동화했으며, 목적지 도달 시 즉시 반환하여 효율성을 높였습니다. BFS의 레벨별 탐색 특성으로 인해 가장 먼저 목적지에 도달하는 경로가 곧 최단 경로가 됩니다.

다른 접근 방식이나 개선 사항이 있다면 댓글로 공유 부탁드립니다!