알고스팟 - 1261번 백준

문제 

문제 난이도 : 골드 4

문제 분류 : 다익스트라 알고리즘

문제 리뷰

다익스트라를 정복해보자아

• 다익스트라는 Greedy + DP 이며, 시간 복잡도는 NlogN(우선 순위 큐를 썼을 경우)

문제 소스코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>
#include <cmath>
#include <string>
#include <deque>
#include <queue>
#include <unordered_map>

using namespace std;

//Global Variable
vector<pair<int, int>> Edges[10010];
int Distance[10010];

//Initializing for Optimization
void Init() 
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
}


void Dijkstra(int Start)
{
    Distance[Start] = 0;
    for (int i = 0; i < 10010; i++)
    {
        Distance[i] = 2100000000;
    }
    priority_queue<pair<int, int>> pq;
    pq.push({ 0,0 });
    while (!pq.empty())
    {
        pair<int, int> Cur = pq.top();
        pq.pop();
        for (int i = 0; i < Edges[Cur.second].size(); i++)
        {
            pair<int, int> Next = Edges[Cur.second][i];
            if (Distance[Next.second] > Next.first - Cur.first)
            {
                Distance[Next.second] = Next.first - Cur.first;
                pq.push({- Distance[Next.second], Next.second });
            }
        }
    }
}

int main()
{
    //Initialize for fast io
    Init();
    //Size Input
    int w, h;
    cin >> w >> h;
    for (int i = 0; i < h; i++)
    {
        string s;
        cin >> s;
        for (int j = 0; j < w; j++)
        {
            bool tmp;
            if (s[j] == '0')
            {
               tmp = false;
            }
            else
            {
                tmp = true;
            }

            if (i > 0)
            {
                Edges[i * w + j].push_back({ tmp, (i - 1) * w + j });
            }
            if (i < h - 1)
            {
                Edges[i * w + j].push_back({ tmp, (i + 1) * w + j });
            }
            if (j > 0)
            {
                Edges[i * w + j].push_back({ tmp, i * w + j - 1 });
            }
            if (j < w - 1)
            {
                Edges[i * w + j].push_back({ tmp, i * w + j + 1 });
            }
        }
    }

    Dijkstra(0);
    if (Distance[w * h - 1] == 2100000000)
    {
        cout << 0;
    }
    else
    {
        cout << Distance[w * h - 1];
    }
}