백준을 풀기전에 알고리즘 공부를 해보아요

다익스트라 알고리즘이 뭐야

그래프를 사용하는 알고리즘에서 최소 비용, 최소 경로, ..를 구해야 하는 경우 사용할 수 있는 알고리즘이다.
최소 비용 중에서도 주어진 두 노드(시작, 끝) 사이의 최소 비용인 경로를 찾을 때 유용하게 사용된다.

로직

비용 -> 1차원 배열에 저장한다. 난 cost[]라고 해볼래

cost배열의 모든 값은 무한대로 초기화되어 있다.

1. 시작 노드와 직접적으로 연결된 모든 정점들의 거리를 비교해서 업데이트 시켜준다.
2. 시작 노드 -> visited 처리
3. visited인 노드와 연결되어 있는 노드들 중 비용이 가장 적게 드는 노드를 선택한다.
4. 해당 노드 -> visited 처리
5. 노드들 사이의 거리를 업데이트 한다.
6. 3~5를 반복한다.

//cost[] : 최소비용 저장 배열 - 초기값: 무한대
//Visited[] : 선택한 노드 표시 배열 - 초기값 - false
//1. 시작 노드와 직접적으로 연결된 모든 정점들의 거리를 비교해서 업데이트 시켜준다.
for (int i=0; i< V;i++){
	cost[i] = MAP[START][i];
    cost[START] = 0;
    //2. 시작 노드 -> visited 처리
    Visited[START] = true;
}

int Find_shortest(){
	int min_cost = INF;
    int min_idx = -1;
    for(int i=0;i<V;i++){
        //3. visited인 노드와 연결되어 있는 노드들 중 비용이 가장 적게 드는 노드를 선택한다.
        if(Visited[i] == true) continue;
        if(cost[i] < min_cost){
            min_cost = cost[i];
            min_idx = i;
        }
    }
}

//4. 해당 노드 -> visited 처리

//5. 노드들 사이의 거리를 업데이트 한다.
int newNode = min_idx; //비용이 가장 적게 드는 노드 선택
void update_cost(int newNode){
  for(int i=0;i<V;i++){
      if(Visited[i]==true) continue;
      if(cost[i] > cost[newNode] + MAP[newNode][i]){
          cost[i] = cost[newNode] + MAP[newNode][i];
      }
  }
}
//반복쓰 - 다익스트라
void Dijkstra(){
	for(int i=0;i<V;i++){
    	cost[i] = MAP[START][i];
        cost[START] = 0;
        Visited[START] = true;
    }
    for(int i=0;i<V-1;i++){
    	int newNode = Find_shortest();
        Visited[newNode] = true;
        update_cost(newNode);
    }
}

-> O(n^2)의 시간복잡도를 갖게 된다.

더 빠른 방법은 우선순위 큐를 사용하는 방법!

우선순위 큐 사용

1. 인접한 간선들을 Queue에 넣는다
2. 최소 힙을 구한다 -> 최소비용이 드는 정점부터 처리

-> O(E logN) (E = 간선의 수, N = 정점의 수) 의 시간복잡도를 갖는다.
(모든 정점들에 대해 최소 힙으로 추출 = O(logN), 모든 간선 확인 O(E) = O(E logN))

=> 아무튼 더 빠르다

void Dijkstra(){
	priority_queue<pair<int,int>> PQ;//값이 클수록 더 높은 우선순위를 가짐
    //{2,3,5}일 때, 위 같이 선언하면 5를 가장 먼저 뽑아서 사용
    PQ.push(make_pair(0,Start);
    cost[Start] = 0;
    
    while(PQ.empty() == 0){
    	int cost = -PQ.top().first; // 최소 힙으로 구현(크기를 반전)
        int current = PQ.top().second;
        PQ.pop();
        
        for(int i=0;i<Vertex[current].size();i++){
        	int next = Vertex[current][i].first;
            int ncost = Vertex[current][i].second;
            
            if(cost[next] > cost + ncost){
            	cost[next] = cost + ncost;
                PQ.push(make_pair(-cost[next], next));
            }
        }
    }
    for(int i=0;i<V;i++){
    	if(cost[i] == INF) cout <<"INF" << endl;
        else cout << cost[i] <<endl;
    }
}

느낀점?
생각해보니 나 이거 학부생때 배웠구나!

오잉 근데
A - B

• C
  일 때 둘 중 최소비용만 선택해서 가면 전체적으로도 최소비용이 될 수 있나?
  -> 노드를 잇는 간선의 가중치 값이 음수일 때는 그렇지 않다!

아래 레퍼런스로 본 블로그 글에 따르면
여기서 다익스트라 알고리즘의 한계가 있다고 한다.
그래프에서 노드를 잇는 간선의 가중치에 음수가 들어가면, 다익스트라 알고리즘은 적용할 수 없다.

백준 1753 최단경로

문제
방향그래프가 주어지면 주어진 시작점에서 다른 모든 정점으로의 최단 경로를 구하는 프로그램을 작성하시오. 단, 모든 간선의 가중치는 10 이하의 자연수이다.

입력
첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1 ≤ K ≤ V)가 주어진다. 셋째 줄부터 E개의 줄에 걸쳐 각 간선을 나타내는 세 개의 정수 (u, v, w)가 순서대로 주어진다. 이는 u에서 v로 가는 가중치 w인 간선이 존재한다는 뜻이다. u와 v는 서로 다르며 w는 10 이하의 자연수이다. 서로 다른 두 정점 사이에 여러 개의 간선이 존재할 수도 있음에 유의한다.

출력
첫째 줄부터 V개의 줄에 걸쳐, i번째 줄에 i번 정점으로의 최단 경로의 경로값을 출력한다. 시작점 자신은 0으로 출력하고, 경로가 존재하지 않는 경우에는 INF를 출력하면 된다.

예제 입력
5 6
1
5 1 1
1 2 2
1 3 3
2 3 4
2 4 5
3 4 6

예제 출력
0
2
3
7
INF

체크&이해를 해보자
가중치가 모두 10이하 자연수
정점V개 = 5, 간선E개 = 6 // V = 5, E = 6
정점 : 1부터 시작 // start = 1
u,v,w ( u-w->v ) (u!=w) (w<=10)
i = 1~V까지, i번 정점V로의 최단 경로값 출력(X: INF)

비용 -> 1차원 배열에 저장한다. 난 cost[]라고 해볼래

0. cost배열의 모든 값은 무한대로 초기화해야 한당

1. 시작 노드와 직접적으로 연결된 모든 정점들의 거리를 비교해서 업데이트 시켜준다.
   vector <pair<int,int>> Vertex[20001];에 저장해둘거다.

시간초과 난 코드😫

//
//  main.cpp
//  1753
//
//  Created by  on 2023/07/05.
//

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#define INF 1000000
#define MAX_VERTEX 20001 // 최대 vertex 개수
#define MAX_EDGE 300001 // 최대 edge 개수

using namespace std;

int Cost[MAX_VERTEX];//비용 저장
int V,E,start;
vector <pair<int,int>> Vertex[MAX_EDGE];//v,w

void Dijkstra(){
    priority_queue<pair<int,int>> PQ;//v,w
    //값이 클수록 더 높은 우선순위를 가짐
    //{2,3,5}일 때, 위 같이 선언하면 5를 가장 먼저 뽑아서 사용
    PQ.push(make_pair(start, 0));
    Cost[start] = 0;//시작점 자신은 0으로 출력
    
    while(!PQ.empty()){
        int cost = -PQ.top().second;//현재 - 비용
        int current = PQ.top().first;//현재 - 도착노드
        PQ.pop();//제거
       
        for(int i=0;i<Vertex[current].size();i++){
            int next = Vertex[current][i].first;//다음 노드
            int ncost = Vertex[current][i].second;//다음 노드까지의 비용
//            cout << "DIJ" << next << ncost << endl;
            if(Cost[next] > cost + ncost){
                Cost[next] = cost + ncost;
                PQ.push(make_pair(next,-Cost[next]));
            }
        }
    }
    for(int i=1;i<=V;i++){
        if(Cost[i] == INF){
            cout << "INF" << endl;
        }
        else{
            cout << Cost[i] << endl;
        }
    }
    
}
int main(){
    
    //인풋 아웃풋 시간 줄여주는 -> 이 차이로 시간초과가 나네,,
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    //입력 받아요
    cin >> V >> E;
    cin >> start;
    
    //비용 INF로 초기화
    for(int i=1;i<=V;i++){
        Cost[i] = INF;
    }
    //노드, 정점 저장
    for(int i=0;i<E;i++){
        int u,w,v;
        cin >> u >> v >> w;
        Vertex[u].push_back(make_pair(v, w));//도착노드, 비용
//        cout << "i=" << i << endl;
    }
    Dijkstra();
    return 0;
}

우선

//인풋 아웃풋 시간 줄여주는 -> 이 차이로 시간초과가 나네,,
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

이 머슬메모리의 중요성을 깨달았고,

vector <pair<int,int>> Vertex[MAX_EDGE];//v,w

void Dijkstra(){
    priority_queue<pair<int,int>> PQ;//v,w

이 부분에서 Vertex 벡터와 PQ 우선순위 큐의 순서를 동일하게 (도착노드,가중치)로 했더니 시간초과가 났다.

맞은 코드🥺

//
//  main.cpp
//  1753
//
//  Created by  on 2023/07/05.
//

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#define INF 1000000
#define MAX_VERTEX 20001 // 최대 vertex 개수
#define MAX_EDGE 300001 // 최대 edge 개수

using namespace std;

int Cost[MAX_VERTEX];//비용 저장
int V,E,start;
vector <pair<int,int>> Vertex[MAX_EDGE];//v,w

void Dijkstra(){
    priority_queue<pair<int,int>> PQ;//w,v
    //값이 클수록 더 높은 우선순위를 가짐
    //{2,3,5}일 때, 위 같이 선언하면 5를 가장 먼저 뽑아서 사용
    PQ.push(make_pair(0, start));
    Cost[start] = 0;//시작점 자신은 0으로 출력
    
    while(!PQ.empty()){
        int cost = -PQ.top().first;//현재 - 비용
        int current = PQ.top().second;//현재 - 도착노드
        PQ.pop();//제거
        
        for(int i=0;i<Vertex[current].size();i++){
            int next = Vertex[current][i].first;//다음 노드
            int ncost = Vertex[current][i].second;//다음 노드까지의 비용
//            cout << "DIJ" << next << ncost << endl;
            if(Cost[next] > cost + ncost){
                Cost[next] = cost + ncost;
                PQ.push(make_pair(-Cost[next], next));
            }
        }
    }
    for(int i=1;i<=V;i++){
        if(Cost[i] == INF){
            cout << "INF" << endl;
        }
        else{
            cout << Cost[i] << endl;
        }
    }
    
}
int main(){
    
    //인풋 아웃풋 시간 줄여주는
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    //입력 받아요
    cin >> V >> E;
    cin >> start;
    
    //비용 INF로 초기화
    for(int i=1;i<=V;i++){
        Cost[i] = INF;
    }
    //노드, 정점 저장
    for(int i=0;i<E;i++){
        int u,w,v;
        cin >> u >> v >> w;
        Vertex[u].push_back(make_pair(v, w));//도착노드, 비용
//        cout << "i=" << i << endl;
    }
    Dijkstra();
    return 0;
}

차이점이라고는

vector <pair<int,int>> Vertex[MAX_EDGE];//v,w

void Dijkstra(){
    priority_queue<pair<int,int>> PQ;//w,v

우선순위 큐에는 (가중치, 도착노드) 순으로 생각해서 푼 것이 다인디,,
왜 위 코드는 시간초과가 나고, 아래 코드는 안나는것인가??
🤯

레퍼런쓰
https://yabmoons.tistory.com/364