[2023 현대모비스 알고리즘 경진대회 본선] 중요한 도로

https://school.programmers.co.kr/learn/courses/30/lessons/214293

프로그래머스

 

 

구현자체는 어렵지 않은데, 최단 경로를 이루는 경로 중 유일 경로임을 판별하여하는 부분이 어려웠던 문제

최근데 다익스트라 문제를 잘 안풀어서, 역방향 탐색할 생각 조차 안 떠올라 시간 좀 썼습니다.

 

 

문제 설명

 

암튼 간단히 요약하자면... 다음과 같다.

1. 도로의 비용은 도로의 길이와 도로의 교통량의 합이다.

2. 간선하나에 대해 교통량이 증가/감소 할 수 있고, 이 교통량에 따라 최소 비용이 바뀔 수 있다.

3. 위 경우, 간선의 교통량이 증가/감소함으로써, 최소 비용에 영향을 주는(최소 비용이 증가/감소하는) 간선을 구해서 오름차순으로 출력한다.

 

즉, 최소 비용을 구하고, 최소 비용을 이루는 간선을 구해야 하며, 해당 간선이 정답에 포함되는지 판별이 필요하다.

 

일단, 최소 비용에 영향을 주는 경우는 다음과 같이 두 가지가 존재한다.

1. 간선의 교통량이 감소하여, 최소 비용이 감소하는 경우

2. 간선의 교통량이 증가하여, 최소 비용이 증가하는 경우

 

1번의 경우, 비교만 해주면 된다.

1번이 시작 정점, N번이 도착 정점이므로, 중간에 a, b 정점을 연결하는 간선에 대해서,

(1에서 a까지의 비용) + (교통량이 0 일 때, a-b비용) + (b에서 N까지의 비용)과 최소 비용을 비교해주면 된다.

물론 1 - b - a - N이 될 수도 있다.

 

2번의 경우, 사전에 기록해둔 path벡터를 역으로 탐색한다.

이때, 최소 비용 간선을 이루는 유일 경로여야, 최소 비용에 영향을 주는 간선이 된다.

BFS로 탐색해주면서, 해당 차례의 큐 사이즈가 1(간선이 단 하나)고, 이어지는 간선이 1개 일 때가 유일 간선이다.

 

코드

#include <string>
#include <vector>
#include <iostream>
#include <queue>
#include <algorithm>
#include <cstring>
#include <unordered_map>
#include <unordered_set>
#include <stack>
#include <map>
#include <set>
using namespace std;
struct Node{
    int n;
    long long cost;
    bool operator<(Node o) const{
        return cost > o.cost;
    }
};
int N, M;
vector<Node> graph[50001];
vector<int> path[50001];
long long answer1[50001];
long long answer2[50001];
long long minCost;
unordered_map<int, int> roadNum[50001];
int result[200001];
unordered_set<int> pathCnt[50001];
int visited[50001];
void dijkstra1()
{
    for(int i = 1; i <= N; ++i)
    {
        answer1[i] = 999999987654321;
    }
    priority_queue<Node> pq;
    pq.push({1, 0});
    answer1[1] = 0;
    while(!pq.empty())
    {
        Node now = pq.top();
        pq.pop();
        if(answer1[now.n] < now.cost) continue;
        for(int i = 0; i < graph[now.n].size(); ++i)
        {
            Node nxt = graph[now.n][i];
            long long nextCost = nxt.cost + answer1[now.n];
            if(nextCost > answer1[nxt.n]) continue;
            else if(nextCost == answer1[nxt.n]){
                path[nxt.n].push_back(now.n);
            }
            else{
                path[nxt.n].clear();
                path[nxt.n].push_back(now.n);
                pq.push({nxt.n, nextCost});
                answer1[nxt.n] = nextCost;
            }
        }
    }
    minCost = answer1[N];
}
void dijkstra2()
{
    for(int i = 1; i <= N; ++i)
    {
        answer2[i] = 999999987654321;
    }
    priority_queue<Node> pq;
    pq.push({N, 0});
    answer2[N] = 0;
    while(!pq.empty())
    {
        Node now = pq.top();
        pq.pop();
        if(answer2[now.n] < now.cost) continue;
        for(int i = 0; i < graph[now.n].size(); ++i)
        {
            Node nxt = graph[now.n][i];
            long long nextCost = nxt.cost + answer2[now.n];
            if(nextCost >= answer2[nxt.n]) continue;
            answer2[nxt.n] = nextCost;
            pq.push({nxt.n, nextCost});
        }
    }
}
void printSummary()
{
    cout << minCost << "\n";
    for(int i = N; i != 1; i = path[i][0])
    {
        for(int j : path[i])
        {
            cout << j << " ";
        }
        cout << "\n";
    }
}
vector<int> solution(int n, vector<vector<int>> roads) {
    N = n;
    M = roads.size();
    for(int i = 1; i <= M; ++i)
    {
        int a = roads[i - 1][0];
        int b = roads[i - 1][1];
        long long l = roads[i - 1][2];
        long long t = roads[i - 1][3];
        graph[a].push_back({b, l + t});
        graph[b].push_back({a, l + t});
        roadNum[a][b] = i;
        roadNum[b][a] = i;
    }
    dijkstra1();
    dijkstra2();
    //printSummary();
    
    for(int i = 1; i <= M; ++i)
    {
        int a = roads[i - 1][0];
        int b = roads[i - 1][1];
        long long l = roads[i - 1][2];
        long long t = roads[i - 1][3];
        if(t == 0) continue;
        if((answer1[a] + answer2[b] + l < minCost) || (answer1[b] + answer2[a] + l < minCost)){
            result[roadNum[a][b]] = 1;
        }
    }
    
    int prev = N;
    queue<int> q;
    q.push(N);
    visited[N] = 1;
    while(!q.empty())
    {
        int qSize = q.size();
        for(int i = 0; i < qSize; ++i)
        {
            int now = q.front();
            q.pop();
            for(int k = 0; k < path[now].size(); ++k)
            {
                int nxt = path[now][k];
                if(path[now].size() == 1 && qSize == 1)
                    pathCnt[nxt].insert(now);
                if(visited[nxt]) continue;
                visited[nxt] = 1;
                q.push(nxt);
            }
        }
    }
    
    for(int i = 1; i <= N; ++i) {
        for(auto j : pathCnt[i]){
            result[roadNum[i][j]] = 1;
        }
    }
    vector<int> answer;
    for(int i = 1; i <= M; ++i) 
    {
        if(result[i]) answer.push_back(i);
    }
    if(answer.size() == 0) answer.push_back(-1);
    return answer;
}