오늘 학습 키워드

• limits

• 구조 분해 선언

• 다익스트라

1. limits

• #include <limits>로 최대, 최소값을 사용할 수 있다.

멤버/함수	설명
max()	해당 타입이 가질 수 있는 최대 유한값
min()	해당 타입이 가질 수 있는 최소 유한값 (정수는 최솟값, 부동소수점은 최소 양수 값)
lowest()	해당 타입이 가질 수 있는 가장 작은 값 (부동소수점은 -max()와 같음)
epsilon()	부동소수점 타입에서 1과 구분 가능한 가장 작은 값

#include <limits>
cout << "int min: " << numeric_limits<int>::min() << "\n";
cout << "int max: " << numeric_limits<int>::max() << "\n";

cout << "float lowest: " << numeric_limits<float>::lowest() << "\n";
cout << "float max: " << numeric_limits<float>::max() << "\n";
cout << "float epsilon: " << numeric_limits<float>::epsilon() << "\n";

// int min: -2147483648
// int max: 2147483647
// float lowest: -3.40282e+38
// float max: 3.40282e+38
// float epsilon: 1.19209e-07

• 이를 이용해서 초기 최대값과 최소값 설정 또는 무한대값을 설정하는데 사용 가능

int MAX = numeric_limits<int>::min();
int MIN = numeric_limits<int>::max();
static const int INF = numeric_limits<int>::max();

2. 구조 분해 선언

• pair 값을 받을 때 값 두 개를 동시에 변수에 할당하는 방법 (C++17이상)

• pair, tupule에만 가능. 벡터, set 안 됨

std::pair<int, int> p = {10, 20};

auto [a, b] = p;	// auto만 사용 가능
auto& [c, d] = p;	// 참조자로 받기도 가능

3. 다익스트라

• 어느 지점 A에서 Z까지 가는 최단경로는 그 중간경로들도 다 최단경로여야 함.

• 만약 중간에 어떤 노드 C를 거치는 최단 경로가 있다면, 출발점에서 C까지 가는 경로도 최단 경로여야 한다.

• 만약 부분 경로가 최단 경로가 아니라면, 더 짧은 경로로 C에 도착할 수 있었을 텐데, 이 경우 전체 경로가 최단 경로일 수 없기 때문이다.

• 따라서 출발점에서부터 시작하여 방문하지 않은 노드 중에서 현재까지 최소 거리를 가진 노드를 선택하는 것을 반복하면 최종목적지까지의 최단경로를 얻을 수 있다.

#include <iostream>
#include <vector>
#include <limits>
#include <queue>
#include <string>

#define N 5

using namespace std;

static const int INF = numeric_limits<int>::max();

string print(int i, const vector<int>& preNode) {
    int a = preNode[i];
    string result = to_string(i);

    while (a != -1) {
        result.push_back(' ');
        result.push_back(a + '0');
        a = preNode[a];
    }
    return string(result.rbegin(), result.rend());
}

int main() {
    // graph의 각 요소는 각 node의 edge들을 저장하는 벡터
    // edge는 { next node, weigh } 형식
    vector <vector< pair<int, int >> > graph(N);
    graph[0].push_back({ 2, 4 });
    graph[0].push_back({ 1, 2 });
    graph[1].push_back({ 2, 1 });
    graph[1].push_back({ 3, 7 });
    graph[2].push_back({ 4, 3 });
    graph[3].push_back({ 4, 1 });

    // 각 node까지의 최단경로 길이
    vector<int> dist(N, INF);
    dist[0] = 0;

    // 해당 Node로 오기 바로 전의 Node
    vector<int> preNode(N, -1);

    // {최단경로 길이, node} 순으로 minHeap을 생성
    priority_queue < pair<int, int>, vector<pair<int, int>>, 
    					greater<pair<int, int>>> minQueue;
    minQueue.push({ 0, 0 });

    int from, from_dist;
    while (!minQueue.empty()) {
        from = minQueue.top().second;
        from_dist = minQueue.top().first;
        minQueue.pop();

        // 도착지에 도착
        if (from == N - 1)
            break;

        if (from_dist > dist[from])
            continue;

        for (const auto& edge : graph[from]) {
            if (dist[edge.first] > dist[from] + edge.second)
            {
                dist[edge.first] = dist[from] + edge.second;
                preNode[edge.first] = from;
                minQueue.push({ dist[edge.first] , edge.first });
            }
        }

    }

    for (int i = 0; i < N; i++) {
        cout << "dist: " << dist[i] << " / path: " << print(i, preNode);
        cout << endl;
    }
}