C++로 구현하는 상하좌우 이동이 가능한 2D 그리드 최소 비용 경로 찾기

2차원 배열이 주어졌을 때, 각 칸에는 해당 칸을 지나가는 데 드는 비용(cost)이 저장되어 있다고 가정해 봅시다. 이때 왼쪽 위(시작점)에서 오른쪽 아래(도착점)까지 이동하면서 소모되는 총 비용이 최소가 되는 경로를 찾는 것이 목표입니다.

단, 이동은 상·하·좌·우 네 방향 모두 허용됩니다. 단순한 동적 계획법(DP)으로는 뒤로 되돌아가는 경로를 처리할 수 없기 때문에, 다익스트라(Dijkstra) 알고리즘을 응용한 접근이 필요합니다.

문제 예시

다음과 같은 5×5 크기의 비용 그리드가 입력으로 주어진다고 해봅시다.

32	101	66	13	19
11	14	48	158	7
101	114	175	12	34
89	126	42	21	141
100	33	112	42	21

이 경우 출력은 340입니다. 예를 들어 (32 + 11 + 14 + 48 + 66 + 13 + 19 + 7 + 34 + 12 + 21 + 42 + 21) = 340이 되는 경로를 따라 이동하기 때문입니다.

해결 접근 방식

이 문제는 각 칸을 정점(vertex)으로, 인접한 네 방향의 이동을 간선(edge)으로 생각하면 가중치가 있는 최단 경로 문제로 환원됩니다. 따라서 우선순위가 보장되는 자료구조(set)를 활용한 다익스트라 알고리즘으로 효율적으로 해결할 수 있습니다.

알고리즘 단계

좌표(x, y)와 현재까지의 거리(distance)를 담는 cell 구조체를 정의합니다.
각 칸까지의 최소 비용을 저장할 크기 row × col의 배열 matrix를 만들고, 모든 값을 무한대(INT_MAX)로 초기화합니다.
상하좌우 이동을 위한 방향 배열 dx = {-1, 0, 1, 0}, dy = {0, 1, 0, -1}를 선언합니다.
cell을 거리 순으로 정렬해 담을 집합(set) st를 만들고, 시작점인 cell(0, 0, 0)을 삽입합니다.
matrix[0][0] := grid[0][0]으로 시작 칸의 비용을 설정합니다.
집합이 빌 때까지 다음 과정을 반복합니다.
- 집합에서 가장 작은(거리가 짧은) 원소 k를 꺼냅니다.
- 네 방향에 대해 인접 좌표 (x, y)를 계산하고, 범위를 벗어나면 건너뜁니다.
- matrix[x][y] > matrix[k.x][k.y] + grid[x][y]라면 더 짧은 경로를 발견한 것이므로,
  - 기존 값이 무한대가 아니었다면 집합에서 기존 cell(x, y, matrix[x][y])을 제거합니다.
  - matrix[x][y]를 새 값으로 갱신하고, 갱신된 cell을 집합에 삽입합니다.
반복이 끝나면 matrix[row - 1][col - 1], 즉 도착점까지의 최소 비용을 반환합니다.

C++ 구현 예제

아래 코드를 통해 실제 동작을 확인해 볼 수 있습니다.

#include <bits/stdc++.h>
using namespace std;
#define ROW 5
#define COL 5
class cell {
    public:
    int x, y;
    int distance;
    cell(int x, int y, int distance) :
    x(x), y(y), distance(distance) {}
};
bool operator<(const cell& a, const cell& b) {
    if (a.distance == b.distance) {
        if (a.x != b.x)
            return (a.x < b.x);
        else
            return (a.y < b.y);
    }
    return (a.distance < b.distance);
}
bool isOk(int i, int j) {
    return (i >= 0 && i < COL && j >= 0 && j < ROW);
}
int solve(int grid[ROW][COL], int row, int col) {
    int matrix[row][col];
    for (int i = 0; i < row; i++)
    for (int j = 0; j < col; j++)
    matrix[i][j] = INT_MAX;
    int dx[] = {-1, 0, 1, 0};
    int dy[] = {0, 1, 0, -1};
    set<cell> st;
    st.insert(cell(0, 0, 0));
    matrix[0][0] = grid[0][0];
    while (!st.empty()) {
        cell k = *st.begin();
        st.erase(st.begin());
        for (int i = 0; i < 4; i++) {
            int x = k.x + dx[i];
            int y = k.y + dy[i]; 
            if (!isOk(x, y))
                continue;
            if (matrix[x][y] > matrix[k.x][k.y] + grid[x][y]){
                if (matrix[x][y] != INT_MAX)
                    st.erase(st.find(cell(x, y, matrix[x][y])));
                    matrix[x][y] = matrix[k.x][k.y] + grid[x][y];
                    st.insert(cell(x, y, matrix[x][y]));
            }
        }
    }
    return matrix[row - 1][col - 1];
}
int main() {
    int grid[ROW][COL] = {
        32, 101, 66, 13, 19,
        11, 14, 48, 158, 7,
        101, 114, 175, 12, 34,
        89, 126, 42, 21, 141,
        100, 33, 112, 42, 21
    };
    cout << solve(grid, ROW, COL);
}

입력

{32, 101, 66, 13, 19,
11, 14, 48, 158, 7,
101, 114, 175, 12, 34,
89, 126, 42, 21, 141,
100, 33, 112, 42, 21
};