[코드트리 조별과제] 2주차 후기 및 다익스트라 각 정점까지의 최단 경로 3 풀이

2주차 후기

삼성 청년 SW 아카데미를 다니면서 도전했던 2번의 B형, Professional 시험 중 한 번은 합격 가능성이 있었던,, 아까운 기억이 있다.
그 때 문제가 아마 그래프 축소 + 다익스트라였던 것으로 기억하는데 아쉽게 다익스트라 알고리즘을 몰라 BFS로 선회, 불합격했었다.

그 이후로도 다익스트라, 프림, 크루스칼 알고리즘 등이 내 발목을 계속 잡길래 학습의 필요성을 느꼈어서,
이번 코드트리 조별과제 이벤트에 참여해 학습해보고 있는데 코드트리 이거,, 참 물건이다.
알고리즘을 학습하면서 가장 불편하고 어려웠던 부분이 동일 알고리즘의 다른 유형 문제를 찾는 것이었는데 코드트리를 쓰면 그런 문제를 안 찾아도 된다는게 정말 편해서 취직 전까지는 사용할 것 같다. 개인적으로 결제할 의향 O

다익스트라 관련 개념과 문제 풀이를 진행 중이다. 정리한 내용을 일부 공유하면

정의 : 시작점부터 모든 정점으로 가는 최단거리를 구하는 알고리즘. 음수 가중치가 없어야 한다
시간 복잡도 : O(ElogV) = 인접 리스트, O(V^2) = 인접 행렬

 

이 정도는 알고 있었는데, 아래 내용이 참 좋다.

모든 정점으로부터 특정 도착점
특정 시작점에서 특정 도착점
사전순으로 가장 앞선 최단거리

위와 같은 유형에 대해 다익스트라를 어떻게 활용할 것인가? 에 대한 고민을 하게 되는 계기였달까..
아직 다익스트라와 어사지만 점점 친해지는 중이다.

문제 풀이

https://www.codetree.ai/missions/8/problems/shortest-path-to-each-vertex-3?&utm_source=clipboard&utm_medium=text

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

위 문제는 다익스트라의 가장 기본형 문제로 단순히 한 정점에서 다른 모든 정점으로 가는 최소값을 구하면 되는 문제이다.
인접 리스트를 이용한 풀이. 간단하니까 코드만 놓고 가겠다.

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

void getInput();
void initData();

int N, M;
priority_queue<int, vector<int>, greater<int>> pq;
vector<vector<vector<int>>> edges;
vector<int> dists;


const int MAX_VALUE = numeric_limits<int>::max();

int main() {
    getInput();
    initData();

    while(!pq.empty()) {
        int s = pq.top();
        pq.pop();

        for (int i = 0; i < edges[s].size(); i++) {
            vector<int> tmp = edges[s][i];
            int next = tmp[0], value = tmp[1];
            
            if (dists[s] + value < dists[next]) {
                dists[next] = dists[s] + value;
                pq.push(next);
            }
        }
    }


    for (int i = 1; i < N; i++) {
        if (dists[i] == MAX_VALUE) cout << -1 << "\n";
        else cout << dists[i] << "\n";
    }
    
    return 0;
}

void initData() {
    dists.resize(N);
    for (int i = 0; i < N; i++) 
        dists[i] = MAX_VALUE;

    dists[0] = 0;
    pq.push(0);
    
    return;
}

void getInput() {
    cin >> N >> M;
    edges.resize(N);

    int start, end, value;
    for (int i = 0; i < M; i++) {
        cin >> start >> end >> value;
        edges[start - 1].push_back({end - 1, value});
    }

    return;
}