알고리즘 스터디 25일차

1. 플로이드

1) 문제

문제 설명
n(2 ≤ n ≤ 100)개의 도시가 있다. 그리고 한 도시에서 출발하여 다른 도시에 도착하는 m(1 ≤ m ≤ 100,000)개의 버스가 있다. 각 버스는 한 번 사용할 때 필요한 비용이 있다.

모든 도시의 쌍 (A, B)에 대해서 도시 A에서 B로 가는데 필요한 비용의 최솟값을 구하는 프로그램을 작성하시오.

입력
첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 주어진다. 버스의 정보는 버스의 시작 도시 a, 도착 도시 b, 한 번 타는데 필요한 비용 c로 이루어져 있다. 시작 도시와 도착 도시가 같은 경우는 없다. 비용은 100,000보다 작거나 같은 자연수이다.

시작 도시와 도착 도시를 연결하는 노선은 하나가 아닐 수 있다.
출력

n개의 줄을 출력해야 한다. i번째 줄에 출력하는 j번째 숫자는 도시 i에서 j로 가는데 필요한 최소 비용이다. 만약, i에서 j로 갈 수 없는 경우에는 그 자리에 0을 출력한다.

2) 문제 분석 및 풀이

1) 설계, 분석

모든 노드에서 모든 노드까지의 거리를 구하는 문제 (다익스트라를 여러번 돌리면 시간이 될까?)
플로이드 워셜을 통해서 문제 해결

2) 풀이

#include <iostream>
#include <vector>
#include <climits>
using namespace std;

int M,N;

int main()
{

    cin >> N;
    cin >> M;

    vector<vector<int>> cost(N+1,vector<int>(N+1,INT_MAX));

    while (M--)
    {
        int from, to, weight;
        cin >> from >> to >> weight;
        cost[from][to] = min(weight, cost[from][to]);
    }

    for (int k = 1; k <= N; k++)
    {
        for (int i = 1; i <= N; i++)
        {
            for (int j = 1; j <= N; j++)
            {
                // i -> k -> j
                if (i==j) continue;
                if (cost[k][j] == INT_MAX) continue;
                if (cost[i][k] == INT_MAX) continue;
                if (cost[i][j] > cost[i][k] + cost[k][j])
                    cost[i][j] = cost[i][k] + cost[k][j];
            }
        }
    }

    for (int i = 1; i <= N; i++)
    {
        for (int j = 1; j <= N; j++)
        {
            int val = cost[i][j] == INT_MAX ? 0 : cost[i][j];
            cout << val << " ";
        }
        cout << '\n';
    }

    return 0;
}

2. 특정한 최단 경로

1) 문제

문제 설명
방향성이 없는 그래프가 주어진다. 세준이는 1번 정점에서 N번 정점으로 최단 거리로 이동하려고 한다. 또한 세준이는 두 가지 조건을 만족하면서 이동하는 특정한 최단 경로를 구하고 싶은데, 그것은 바로 임의로 주어진 두 정점은 반드시 통과해야 한다는 것이다.

세준이는 한번 이동했던 정점은 물론, 한번 이동했던 간선도 다시 이동할 수 있다. 하지만 반드시 최단 경로로 이동해야 한다는 사실에 주의하라. 1번 정점에서 N번 정점으로 이동할 때, 주어진 두 정점을 반드시 거치면서 최단 경로로 이동하는 프로그램을 작성하시오.

입력
첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존재하며, 그 거리가 c라는 뜻이다. (1 ≤ c ≤ 1,000) 다음 줄에는 반드시 거쳐야 하는 두 개의 서로 다른 정점 번호 v1과 v2가 주어진다. (v1 ≠ v2, v1 ≠ N, v2 ≠ 1) 임의의 두 정점 u와 v사이에는 간선이 최대 1개 존재한다.

시작 도시와 도착 도시를 연결하는 노선은 하나가 아닐 수 있다.

출력

첫째 줄에 두 개의 정점을 지나는 최단 경로의 길이를 출력한다. 그러한 경로가 없을 때에는 -1을 출력한다.

2) 문제 분석 및 풀이

1) 설계, 분석

특정한 경로를 반드시 거쳐야하는 문제
u->v 인데 중간에 k를 거쳐야하면
u->k1->k2->v 인데 u->k1의 최소경로, k1->k2의 최소 경로 k2->v 최소경로를 구하여 더한다.
(단 무방향 그래프라 반대 방향도 생각)

2) 풀이

#include <iostream>
#include <vector>
#include <climits>
#include <queue>
#include <unordered_map>
using namespace std;

int N,E;
int u,v;
// dist, nodeNum
vector<vector<int>> dijkstraVec;
vector<bool> visited;
unordered_map<int, vector<pair<int, int>>> adjList;

void dijkcstra(int start)
{
    visited.clear();
    visited.resize(N+1,false);
    dijkstraVec.clear();
    dijkstraVec.resize(N+1,vector<int>(2, INT_MAX));
    dijkstraVec[start][0] = 0;
    dijkstraVec[start][1] = start;

    auto cmp = [](const pair<int,int>& a, const pair<int,int>& b){
        return a.first > a.second;
    };
    priority_queue<pair<int, int>, vector<pair<int, int>>, decltype(cmp)> pq(cmp);

    pq.push({0, start});

    while (!pq.empty())
    {
        auto [dist, currNode] = pq.top(); pq.pop();

        for (auto [v, weight] : adjList[currNode])
        {
            int start2v = dijkstraVec[v][0];
            int start2currNode =  dijkstraVec[currNode][0];
            int currNode2v = weight;
            if (start2v > start2currNode + currNode2v)
            {
                dijkstraVec[v][0] = start2currNode + currNode2v;
                dijkstraVec[v][1] = currNode;
                pq.push({dijkstraVec[v][0], v});
            }
        }
    }
}

int main()
{

    cin >> N >> E;
    for (int i=0; i<E; i++)
    {
        int from, to, weight;
        cin >> from >> to >> weight;
        adjList[from].push_back({to, weight});
        adjList[to].push_back({from, weight});
    } 
    cin >> u >> v;
    if (adjList[u].size() == 0 || adjList[u].size() == 0)
    {
        cout << -1 << "\n";
        return 0;
    }

    int start2u;
    int u2v;
    int v2E;

    int valA=0;
    int valB=0;
    dijkcstra(1);
    valA += dijkstraVec[u][0];
    valB += dijkstraVec[v][0];

    dijkcstra(u);
    if (dijkstraVec[v][0] == INT_MAX)
        valA = dijkstraVec[v][0];
    else 
        valA = valA + dijkstraVec[v][0];

    if (dijkstraVec[N][0] == INT_MAX)
        valB = dijkstraVec[N][0];
    else
        valB = valB + dijkstraVec[N][0];

    dijkcstra(v);
    if (dijkstraVec[N][0] == INT_MAX)
        valA = dijkstraVec[N][0];
    else 
        valA = valA + dijkstraVec[N][0];

    if (dijkstraVec[u][0] == INT_MAX)
        valB = dijkstraVec[u][0];
    else
        valB = valB + dijkstraVec[u][0];

    int answer=-1;
    if ((valA < 0 || valA == INT_MAX) && (valB < 0 || valB == INT_MAX)) answer = -1;
    else if ((valA < 0 || valA == INT_MAX))
    {
        answer = valB;
    }
    else if ((valB < 0 || valB == INT_MAX))
    {
        answer = valA;
    }
    else
    {
        answer = min(valA, valB);
    }

    cout << answer << "\n";

    return 0;
}