[BOJ알고리즘, C++]#1261_알고스팟, 최단 경로 알고리즘, 다익스트라 알고리즘

 

#1. 문제

 

 

---

 

#2. 풀이

 

1. 최단 경로 알고리즘

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

 

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

[종류]

1. 다익스트라 알고리즘 : 우선순위 큐, BFS
2. 벨만-포드 알고리즘 : 음의 가중치, 간선 중심, N-1번과 N번
3. 플로이드 알고리즘 : 음수 가중치, 세 개의 중첩 for-반복문, DP

 

2. 다익스트라 알고리즘

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

 

[정의] : 다익스트라 알고리즘은 가중치 그래프 내 "단일-출발" 최단 경로를 찾는 알고리즘입니다.

[특징] : 우선순위 큐를 활용해 인접 정점의 탐색 순서를 결정하고, 출발 정점으로부터 각 정점의 최단 경로를 업데이트합니다.

 

3. 현재 방과 인접한 네 개의 방!

 

1. 다익스트라 알고리즘을 정의합니다. 
2. 현재 방에 인접한 네 개의 방을 순회하며, 각 방의 최소 비용을 업데이트합니다.

 

---

 

#3. 코드

 

#include <iostream>
#include <queue>
#include <vector>
#define INF 1e9
using namespace std;

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

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

    int N, M;
    cin >> M >> N;

    vector<vector<int>> maze(N, vector<int>(M, 0));
    vector<vector<int>> dist(N, vector<int>(M, INF));
    for (int i = 0; i < N; i++)
    {
        string row;
        cin >> row;
        for (int j = 0; j < M; j++)
        {
            maze[i][j] = row[j] - '0';
        }
    }

    priority_queue<pair<int, pair<int, int>>, vector<pair<int, pair<int, int>>>, greater<pair<int, pair<int, int>>>> pq;
    pq.push({0, {0, 0}});
    dist[0][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 (dist[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 >= M)
                continue;

            int nextCost = cost + maze[nx][ny];
            if (dist[nx][ny] > nextCost)
            {
                dist[nx][ny] = nextCost;
                pq.push({nextCost, {nx, ny}});
            }
        }
    }

    cout << dist[N - 1][M - 1] << '\n';

    return 0;
}

 

---