[LeetCode] 1615. Maximal Network Rank

https://leetcode.com/problems/maximal-network-rank/description/

Maximal Network Rank - LeetCode

문제 유형 : 그래프

문제 난이도 : Medium

 

문제

There is an infrastructure of n cities with some number of roads connecting these cities. Each roads[i] = [ai, bi] indicates that there is a bidirectional road between cities ai and bi.

The network rank of two different cities is defined as the total number of directly connected roads to either city. If a road is directly connected to both cities, it is only counted once.

The maximal network rank of the infrastructure is the maximum network rank of all pairs of different cities.

Given the integer n and the array roads, return the maximal network rank of the entire infrastructure.

 

인프라에 n개의 도시와 연결 정보가 담긴 road가 있습니다.

 

두 다른 도시간의 네트워크 랭크는 두 도시에서 다른 도시로 직접적으로 연결된 길들의 개수입니다.

만약 두 도시가 직접 연결되어 있다면, 하나만 인정됩니다(중복 연결은 인정하지 않습니다)

이 인프라의 최대 도시 네트워크 랭크를 구하시오.

 

풀이

도시를 노드라고 쳤을 때, 노드의 차수를 담는 degrees 배열을 만든다. degrees[i]는 도시 i의 차수를 의미한다.

 

roads를 한 번씩 순회하면서 연결 정보를 각 노드의 차수로 변환한다. ([0,1]이라면 degrees[0]과 degrees[1]에 각각 1씩 추가, 이를 반복)

 

그 다음, 모든 두 도시의 최대 네트워크 랭크를 구하며, 최댓값을 갱신시킨다. (각 최대 네트워크 랭크는 직접적으로 연결되었는지 확인 후, 직접적으로 연결되어있다면 1을 빼줘야 한다.)

 

이 인프라의 최대 네트워크 랭크를 반환한다.

 

코드

C++

class Solution {
public:
    int maximalNetworkRank(int n, vector<vector<int>>& roads) {
        vector<int> degrees (n, 0);
        set<pair<int, int>> directConnections;

        for(auto road : roads) {
            degrees[road[0]]++;
            degrees[road[1]]++;
            directConnections.insert({min(road[0], road[1]), max(road[0], road[1])});
        }

        int maxRank = 0;
        for(int i = 0; i < n; i++) {
            for(int j = i+1; j < n; j++) {
                int rank = degrees[i] + degrees[j];

                if(directConnections.find({i, j}) != directConnections.end()) {
                    rank--;
                } 

                maxRank = max(maxRank, rank);
            }
        }

        return maxRank;

    }
};

 

Python3

class Solution:
    def maximalNetworkRank(self, n: int, roads: List[List[int]]) -> int:
        degrees = [0] * n
        direct_connections = set()

        for a,b in roads:
            degrees[a] += 1
            degrees[b] += 1
            direct_connections.add((min(a,b), max(a,b)))

        maxRank = 0

        for i in range(n):
            for j in range(i+1, n):
                rank = degrees[i]+degrees[j]

                if(i, j) in direct_connections:
                    rank -= 1

                maxRank = max(maxRank, rank)

        return maxRank

 

Java

class Solution {
    public int maximalNetworkRank(int n, int[][] roads) {
        int[] degrees = new int[n];
        Set<Pair> directConnections = new HashSet<>();

        for(int[] road : roads) {
            degrees[road[0]]++;
            degrees[road[1]]++;
            directConnections.add(new Pair(Math.min(road[0],road[1]), Math.max(road[0],road[1])));
        }
        
        int maxRank = 0;
        for(int i = 0; i < n; i++) {
            for(int j = i+1; j < n; j++) {
                int rank = degrees[i] + degrees[j];

                if(directConnections.contains(new Pair(i, j))) {
                    rank--;
                }

                maxRank = Math.max(maxRank, rank);
            }
        }

        return maxRank;
    }
}