[LeetCode] 2699. Modify Graph Edge Weights

https://leetcode.com/problems/modify-graph-edge-weights/description/?envType=daily-question&envId=2024-08-30

leetcode - Modift Graph Edge Weights

문제 유형 : 우선순위 큐, 다익스트라, 최단거리

문제 난이도 : Hard

 

문제

You are given an undirected weighted connected graph containing n nodes labeled from 0 to n - 1, and an integer array edges where edges[i] = [ai, bi, wi] indicates that there is an edge between nodes ai and bi with weight wi.

Some edges have a weight of -1 (wi = -1), while others have a positive weight (wi > 0).

Your task is to modify all edges with a weight of -1 by assigning them positive integer values in the range [1, 2 * 109] so that the shortest distance between the nodes source and destination becomes equal to an integer target. If there are multiple modifications that make the shortest distance between source and destination equal to target, any of them will be considered correct.

Return an array containing all edges (even unmodified ones) in any order if it is possible to make the shortest distance from source to destination equal to target, or an empty array if it's impossible.

Note: You are not allowed to modify the weights of edges with initial positive weights.

 

무방향 가중치 그래프가 있다. n개의 노드가 숫자 0부터 n-1까지 라벨링되어있다.

edges[i] = [ai, bi, wi]인데, ai와 bi사이의 가중치가 wi라는 뜻이다.

일부 가중치는 -1일 수 있고, 나머지는 양수이다.

우리는 -1짜리 가중치 간선들을 모두 양수로 바꿔주어야 한다.

그리고 또 만족해야 하는 조건은, source부터 destination까지의 최단 거리가 target과 같아야 한다는 것이다.

조건을 만족하고록 간선을 수정하여 반환하시오.

 

중복되는 답이 여럿 있을 수 있습니다. 한 가지 케이스로만 반환하시오.

안된다면, 빈 배열을 반환하시오.

 

풀이

두 번의 다익스트라를 사용하여 풀어야 한다는 것까지는 맞췄다만, 디테일한 부분에서 미끄러져서 풀지 못하다가 답안을 확인했다.

https://leetcode.com/problems/modify-graph-edge-weights/solutions/5708699/dijkstra-s-with-tc-o-e-v-log-v-beats-100-in-all-languages/?envType=daily-question&envId=2024-08-30

참고 답안은 위 링크 참조.

그리고 왜 내가 기존에 "우선순위큐를 이용한 다익스트라 알고리즘"에서 항상 "최초 도달하는 노드에 대해 그 길이 최단경로"라고 생각하고있었는지 모르겠다.

사실은 "이후 더 비싼 경로들은 기각한다"라는 로직이 맞는데 말이다.

우선순위 큐와 다음 행선지의 가중치가 얼마나 저렴한지는 알아낼 수 없기 때문이다.

 

두 번의 다익스트라를 사용하는 이유는 다음과 같다:

에지 케이스에 대비 - 예를 들면, 최단경로가 존재하는데, 그 경로의 비용이 target보다 큰 경우 등.

그리고, 기본적으로 모든 간선이 1 이상이 되어야 하기에, 최소 1을 분배하는 과정이 필요한 것이다.

0번째 다익스트라에서는 모든 -1간선들을 1로 간주시켜서 계산시켜볼 예정이다.

1번째 다익스트라에서는 최단 경로의 코스트를 target으로 만들기 위해서 추가적으로 가중치를 분배하는 과정이다.

 

1. 간선을 가지고 인접리스트 만들기

보통 주어진 간선으로 인접리스트를 만들 때, {행선지, 가중치}와 같은 식으로 저장하는데,

여기서는 -1인경우에 특수 처리가 필요한데다가, 다익스트라를 두 번 사용하므로, {행선지, 간선 인덱스}를 저장한다.

거기다가, 원본 edges에 대해 수정하고 반환해야 하기 때문이다.

 

2. 최단 거리 테이블 만들기

예를 들어, dist[node][0] = 0번째 다익스트라에서의 source로부터 Node까지의 최단거리를 저장하자.

dist[source][0] = dist[source][1] = 0으로 초기화해주는 것도 잊지 말자.

 

3. 0번째 다익스트라 수행

다익스트라를 수행하면서, 모든 -1 간선에 1로 대체했다고 가정하고 진행한다.

 

4. 정수 diff = target - dist[destination]를 구한다. 이 정수 diff가 음수라면, 유효하지 않으므로 빈 배열을 반환한다.

diff의 의미는 1로 간주했던 간선들에게 추가로 분배해야 하는 가중치의 양을 말한다.

 

5. 1번쨰 다익스트라 수행

다익스트라를 수행하면서, 이번에는 기존 -1이던 간선을 완전히 바꿔줄 것이다.

newWeight = diff + dist[nextNode][0] - dist[currNode][1]으로 대체할 것인데, 

이는 (diff + 0번째 다익스트라에서의 nextNode까지의 최단거리 - 현재 다익스트라에서의 최단거리)인데, 

이 연산으로, 사실상 최단 경로 내에서의 첫 -1짜리 간선에 나머지 diff만큼의 가중치를 모두 주는 것이다.

이 이후로는 difs[currNode][1]이 커져서 newWeight가 1보다 작아져서 유효하게 대체하지는 못할 것이기 때문이다.

그래서 나머지 최단 경로내의 간선들은 1이다.

최단 경로 이외의 간선에는 무슨 숫자가 들어가는 상관없으니, newWeight를 넣어도 무방하겠다.

 

6. 나머지 모든 음수 간선에 대해 1을 채워주고, edges를 반환해주자.

만약 dist[destnation][1]이 target보다 작으면, 유효하지 않은 결과이므로 빈 배열을 반환하자.

(기각된 경로에 대해 음수 간선이 있었을 수 있다)

 

코드

C++

class Solution {
private:
    void dijkstra(const vector<vector<pair<int, int>>> &graph, vector<vector<int>> &edges, vector<vector<int>> &dist, int source, int difference, int run) {
        int n = graph.size();
        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;
        pq.push({0, source});
        dist[source][run] = 0;

        while(!pq.empty()) {
            auto [currDist, currNode] = pq.top();
            pq.pop();
            if (currDist > dist[currNode][run]) continue;

            for (auto &next : graph[currNode]) {
                int nextNode = next.first;
                int edgeIdx = next.second;
                int weight = edges[edgeIdx][2];

                if (weight == -1) weight = 1;

                if (run == 1 && edges[edgeIdx][2] == -1) {
                    int newWeight = difference + dist[nextNode][0] - dist[currNode][1];
                    if(newWeight > weight) {
                        edges[edgeIdx][2] = weight = newWeight;
                    }
                }

                if (dist[nextNode][run] > dist[currNode][run] + weight) {
                    dist[nextNode][run] = dist[currNode][run] + weight;
                    pq.push({dist[nextNode][run], nextNode});
                }
            }
        }
    }
public:
    vector<vector<int>> modifiedGraphEdges(int n, vector<vector<int>>& edges, int source, int destination, int target) {
        vector<vector<pair<int, int>>> graph(n);

        for(int i = 0; i < edges.size(); i++) {
            int src = edges[i][0];
            int dst = edges[i][1];
            graph[src].push_back({dst, i});
            graph[dst].push_back({src, i});
        }

        vector<vector<int>> dist(n, vector<int>(2, INT_MAX));
        dist[source][0] = dist[source][1] = 0;

        dijkstra(graph, edges, dist, source, 0, 0);
        int diff = target - dist[destination][0];
        if(diff < 0) return {};
        dijkstra(graph, edges, dist, source, diff, 1);
        if(dist[destination][1] < target) return {};

        for (auto &edge : edges) {
            if(edge[2] == -1) edge[2] = 1;
        }
        return edges;
    }
};