알고리즘 :: 이것이 코딩 테스트다 :: 최단거리 :: Q39 :: 화성 탐사

문제

화성 탐사 기계가 존재하는 공간은 N x N 2차원 공간이며 각각의 칸을 지나기 위한 비용이 존재한다. 가장 왼쪽 칸에서 가장 오른쪽 아래 칸인 위치로 이동하는 최소 비용을 출력하는 프로그램을 작성하세요.

문제접근

• 임의의 시작점이 주어지고 임의의 도착점까지의 최단 경로(최소 비용)를 구하는 전형적인 다익스트라 알고리즘 문제다.
• 다익스트라 알고리즘을 그대로 구현하면 해결할 수 있다.

코드

#include <iostream>
#include <queue>
#include <tuple>
using namespace std;
using t = tuple<int, int, int>;

static int T, N, mars[125][125], dist[125][125];
static constexpr int moving[4][2] = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};

void dijkstra() {
	// tuple (y좌표, x좌표, cost)
    priority_queue<t, vector<t>, greater<t>> pq;
    pq.push({0, 0, mars[0][0]});
    dist[0][0] = mars[0][0];

    while(!pq.empty()) {
        int y, x, cost; tie(y, x, cost) = pq.top();
        pq.pop();
        if (dist[y][x] < cost) continue;
        
        for (int i = 0; i < 4; ++i) {
            int ny = y + moving[i][0], nx = x + moving[i][1];
            if (ny < 0 || ny >= N || nx < 0 || nx >= N) continue;
			
            int newCost = cost + mars[ny][nx];
            if (dist[ny][nx] > newCost) {
                dist[ny][nx] = newCost;
                pq.push({ny, nx, newCost});
            }
        }
    }
}

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
    cin >> T;
    while(T--) {
        cin >> N;
        for (int y = 0; y < N; ++y)
            for (int x = 0; x < N; ++x) cin >> mars[y][x];
        
		// 2차원 배열의 모든 원소를 초기화한다.
        fill(&dist[0][0], &dist[N][N], 1e9);
        dijkstra();
        cout << dist[N - 1][N - 1] << '\n';
        fill(&mars[0][0], &mars[N][N], 0);
    }
}

입력 예시

3
3
5 5 4
3 9 1
3 2 7
5
3 7 2 0 1
2 8 0 9 1
1 2 1 8 1
9 8 9 2 0
3 6 5 1 5
7
9 0 5 1 1 5 3
4 1 2 1 6 5 3
0 7 6 1 6 8 5
1 1 7 8 3 2 3
9 4 0 7 6 4 1
5 8 3 2 4 8 3
7 4 8 4 8 3 4

20
19
36