CPP12

JUSTICE_DER·2023년 8월 9일

⏲ CPP - 코딩테스트

목록 보기

16/41

1. 17396 - Dijkstra

https://www.acmicpc.net/problem/17396

제일 싫어하는 문제 유형이다.
필요한 요건만 설명하면 되는데, 불필요한 서술을 굉장히 많이 붙였다.

간단히 요약하면, 방문하면 안되는 정점을 제외하고
최단거리를 구하면 끝인 문제다.

방문하면 안되는 정점은 제시된다.
하지만 N번째 정점은 마지막이므로 통과하도록 해야한다.

해결

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

using namespace std;

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);

    int N, E;
    cin >> N >> E;

    bool cantGo[100001];
    for(int i=0; i<N; i++)
    {
        cin >> cantGo[i];
    }
    cantGo[N-1] = false;

    vector<pair<long long, long long>> connection[100001];

    while(E--)
    {
        long long a, b, w;
        cin >> a >> b >> w;

        // 양방향
        connection[a].push_back({w, b});
        connection[b].push_back({w, a});
    }

    const long long INF = numeric_limits<long long>::max();
    long long d[N];
    fill(d, d+N+1,INF);

    priority_queue<pair<long, long>, vector<pair<long, long>>, greater<pair<long, long>>> pq;
    d[0] = 0;
    pq.push({d[0], 0});

    while(!pq.empty())
    {
        long long cur_Dist = pq.top().first;
        long long cur_Idx = pq.top().second;

        pq.pop();


        if(d[cur_Idx] < cur_Dist){
            continue;
        }

        for(auto next : connection[cur_Idx])
        {
            long long next_W = next.first;
            long long next_Idx = next.second;

            // 해당 조건이 문제 핵심
            if(cantGo[next_Idx])
            {
                //cout << "cant Go :" << next_Idx << "\n";
                continue;
            }

            if(d[next_Idx] <= next_W + d[cur_Idx])
            {
                continue;
            } 
            else
            {
                d[next_Idx] = next_W + d[cur_Idx];
                pq.push({d[next_Idx], next_Idx});
            }
        }
    }

    if(d[N-1] == INF)
    {
        cout << -1;
        return 0;
    }
    cout << d[N-1];

    return 0;   
}

풀이

알고리즘 구현은 상당히 단순했다.
하지만 자료형을 long long을 사용해야만 풀이가 되는 문제였다.

가중치의 합이 100억을 넘는 값이 나올 수 있어서,
21억까지 표현하는 int로는 한계가 있었다.

보면 long은 cpp에서 int와 똑같이 4바이트이다.
따라서 long도 아니고 long long을 사용해야만 해결되는 문제였다.
노드 개수는 굳이 long long으로 하지 않아도 된다

구현이 간단해보인다고 굳이 하지 않아도 된다고
생각하지 않아서 얻은 지식이다.

항상 모든 문제에는 배울점이 있다.

2. 1238 - Dijkstra

https://www.acmicpc.net/problem/1238

해당 문제를 마지막으로 Dijkstra 알고리즘을 마치려고 한다.
문제를 마치면 다음에는 플로이드-워셜 알고리즘을 배워볼까..

문제는 해석하자면 다음과 같다.
각 정점으로부터 특정 정점으로 갔다가 다시 돌아오는 비용이
가장 큰 그 비용을 출력하면 된다.

다시 돌아오는 비용을 구하기 위해서는 또 다익스트라를 사용해야만 한다
(양방향 길이 아니기 때문ㄴ)

따라서 정점마다 다익스트라를 2번 사용하여 계산하고,
합이 최대인 값을 반환하면 될것이다.

시도

되지 않았다.

2로 가는 최단거리를 구해야하는데
3-1-2 << 해당 값이 제대로 출력이 되지 않았다.

다시 사이클로 들어가고 있었던 것이다.

위처럼 수정했다. 어우.. 1시간이 걸렸다.

해결

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

using namespace std;

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

int N, E, X;
vector<pair<int, int>> connection[1001]; // 1~1000 N
int d[1001];

priority_queue<int> goback;

int Dijkstra(int, int);

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> N >> E >> X;

    while (E--)
    {
        int from, to, w;
        cin >> from >> to >> w;
        connection[from].push_back({w, to});
    }

    for (int i = 1; i <= N; i++)
    {
        int sum = 0;
        sum += Dijkstra(i, X);
        // cout << "1st " << i << " : " << sum << "\n";
        sum += Dijkstra(X, i);
        // cout << "2nd " << i << " : " << sum << "\n";
        goback.push(sum);
    }

    cout << goback.top();
    return 0;
}

int Dijkstra(int start, int end)
{
    if (start == end)
    {
        return 0;
    }

    fill(d, d + N + 1, INF);
    d[start] = 0;
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;

    pq.push({d[start], start});

    while (!pq.empty())
    {
        int cur_Dist = pq.top().first;
        int cur_Idx = pq.top().second;

        pq.pop();

        if (d[cur_Idx] != cur_Dist)
        {
            continue;
        }

        for (auto next : connection[cur_Idx])
        {
            int next_W = next.first;
            int next_Idx = next.second;

            if (d[next_Idx] <= cur_Dist + next_W)
            {
                continue;
            }
            else
            {
                d[next_Idx] = cur_Dist + next_W;
                pq.push({d[next_Idx], next_Idx});
            }
        }
    }
    return d[end];
}