[LeetCode] 2285. Maximum Total Importance of Roads

https://leetcode.com/problems/maximum-total-importance-of-roads/description/

leetcode - Maximum Total Importance of Roads

문제 유형 : 그리디, 우선순위 큐, 그래프

문제 난이도 : Medium

 

문제

You are given an integer n denoting the number of cities in a country. The cities are numbered from 0 to n - 1.

You are also given a 2D integer array roads where roads[i] = [ai, bi] denotes that there exists a bidirectional road connecting cities ai and bi.

You need to assign each city with an integer value from 1 to n, where each value can only be used once. The importance of a road is then defined as the sum of the values of the two cities it connects.

Return the maximum total importance of all roads possible after assigning the values optimally.

 

도시의 개수인 정수 n을 받습니다.

0부터 n-1로 번호가 매겨져 있습니다.

당신은 2차원배열 roads를 받습니다. roads[i] = [a_i, b_i]는 a_i부터 b_i 사이에 쌍방향 연결이 존재함을 말합니다.

각 도시에 1부터 n까지 가중치를 부여해야 합니다. 각 숫자는 한 번씩만 쓰입니다.

도로의 중요도는 두 도시의 가중치의 합입니다.

모든 도로의 중요도의 최대 합을 구하시오.

 

풀이

각 노드의 차수를 구해서 우선순위 큐에 넣고, 우선순위 큐에서 값을 하나씩 없애며 n부터 1까지 순차적으로곱해서 누적시킨다.

 

코드

C++

#pragma GCC optimize("03", "unroll-loops");
static const int __ = [](){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    return 0;
}();

class Solution {
public:
    long long maximumImportance(int n, vector<vector<int>>& roads) {
        vector<int> indegree(n, 0); // indegree[idx] = indegree value. ex1) indegree[2] = 4;
        priority_queue<int> pq;
        long long ans = 0;

        for(const auto &road : roads) {
            indegree[road[0]]++;
            indegree[road[1]]++;
        }
        
        for(int i = 0; i < n; i++) {
            pq.push(indegree[i]);
        }
        
        while(!pq.empty()) {
            ans += (long long)pq.top() * (n--);
            pq.pop();
        }

        return ans;
    }
};