[BOJ알고리즘, C++]#4485_녹색 옷 입은 애가 젤다지?, 최단 경로 알고리즘, 길 찾기 알고리즘, 다익스트라

 

#1. 문제

 

 

---

 

#2. 풀이

 

1. 최단 경로 알고리즘

[알고리즘]#2_길 찾기 알고리즘

 

[정의] : 최단 경로 알고리즘은 가중치 그래프 내 출발점과 도착점 사이 가중치가 최소가 되는 경로를 찾는 알고리즘입니다.

[종류]

1. 다익스트라 : 우선순위 큐 활용, BFS
2. 벨만-포드 : 간선 중심, N-1번과 N번
3. 플로이드 : 3번의 중점 for-반복문, DP

 

2. 다익스트라

[정의] : 다익스트라 알고리즘은 양의 가중치를 갖는 그래프 내 특정 출발점으로부터 다른 모든 정점까지의 최단 경로를 찾는 알고리즘입니다. 

[특징] : 다익스트라 알고리즘은 우선순위 큐를 통해 인접 정점의 탐색 순서를 결정합니다.

 

3. 다익스트라를 통해 1x1 출발 정점으로부터 최소 비용 값을 업데이트!

 

1. 출발 정점을 [1][1]로 하는 다익스트라를 수행하고, [N-1][N-1]의 최소 비용 값을 출력합니다.

 

---

 

#3. 코드

 

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

typedef pair<int, int> p;

int N, problemNum = 1;

int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};

int dijkstra(vector<vector<int>> &graph)
{
    vector<vector<int>> rupee(N, vector<int>(N, INT_MAX));
    priority_queue<pair<int, p>, vector<pair<int, p>>, greater<pair<int, p>>> pq;

    rupee[0][0] = graph[0][0];
    pq.push({rupee[0][0], make_pair(0, 0)});

    while (!pq.empty())
    {
        int cost = pq.top().first;
        int x = pq.top().second.first;
        int y = pq.top().second.second;

        pq.pop();

        if (rupee[x][y] < cost)
            continue;

        for (int i = 0; i < 4; ++i)
        {
            int nx = x + dx[i];
            int ny = y + dy[i];

            if (nx < 0 || nx >= N || ny < 0 || ny >= N)
                continue;

            int new_cost = cost + graph[nx][ny];
            if (rupee[nx][ny] > new_cost)
            {
                pq.push({new_cost, make_pair(nx, ny)});
                rupee[nx][ny] = new_cost;
            }
        }
    }
    return rupee[N - 1][N - 1];
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    while (true)
    {
        cin >> N;
        if (N == 0)
            break;

        vector<vector<int>> graph(N, vector<int>(N));

        for (int i = 0; i < N; ++i)
        {
            for (int j = 0; j < N; ++j)
                cin >> graph[i][j];
        }

        // 다익스트라
        cout << "Problem" << ' ';
        cout << problemNum << ':' << ' ';
        cout << dijkstra(graph) << '\n';

        problemNum++;
    }

    return 0;
}

 

---