미로 만들기 - 2665번 백준

문제

문제 난이도 : 골드 4

문제 분류 : 다익스트라

 

문제 코드

#include <iostream>
#include <vector>
#include <string>
#include <cmath>
#include <algorithm>
#include <queue>
#include <unordered_set>
#include <memory.h>

using namespace std;

int Distance[3000];
vector<pair<int, int>> Edges[3000];
const int MYINTMAX{ 2140000000 };
bool Visited[3000];
void Init()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    std::cout.tie(NULL);
}
void Dijkstra(int s, int e) {
    for (int i = 0; i < 3000; i++) {
        Distance[i] = MYINTMAX;
    }
    Distance[s] = 0;
    priority_queue<pair<int, int>> PQ;
    PQ.push({ 0,0 });

    while (!PQ.empty()) {
        
        int CurDist = - PQ.top().first;
        int CurIndex = PQ.top().second;
        PQ.pop();
        if (Visited[CurIndex] == true) continue;
        Visited[CurIndex] = true;
        
        for (int i = 0; i < Edges[CurIndex].size(); i++) {
            int NextDist = Edges[CurIndex][i].first;
            int NextIndex = Edges[CurIndex][i].second;
            if (Distance[NextIndex] >= NextDist + CurDist) {
                Distance[NextIndex] = NextDist + CurDist;
                PQ.push({ -Distance[NextIndex], NextIndex });
            }
        }
    }

}

int main()
{
    Init();
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        string s;
        cin >> s;
        for (int j = 0; j < n; j++) {
            if (s[j] == '0') {
                if (i > 0) {
                    Edges[i * n + j].push_back({ 1, (i-1) * n + j });
                }
                if (j > 0) {
                    Edges[i * n + j].push_back({ 1, i * n + (j - 1) });
                }
                if (i < n - 1) {
                    Edges[i * n + j].push_back({1, (i + 1)* (n) + j });
                }
                if (j < n - 1) {
                    Edges[i * n + j].push_back({ 1, i * n + (j + 1) });
                }
            }
            else {
                if (i > 0) {
                    Edges[i * n + j].push_back({ 0, (i-1) * (n) + j });
                }
                if (j > 0) {
                    Edges[i * n + j].push_back({ 0, i * n + (j - 1) });
                }
                if (i < n - 1) {
                    Edges[i * n + j].push_back({ 0, (i +1)* (n) + j });
                }
                if (j < n - 1) {
                    Edges[i * n + j].push_back({ 0, i * n + (j + 1) });
                }
            }
        }
    }

    Dijkstra(0, n * n);
    cout << Distance[n * n - 1];


}