<Medium> Maximal Network Rank (LeetCode : C#)

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

📕 문제 설명

n개의 도시와 도로가 있을 때 roads[i]는 두 도시 사이에 양방향 도로가 있음을 나타낸다.
roads[i] = [a_i, b_i]

두 도시에 대한 network rank란 각 도시에 대해 직접적으로 연결된 도로의 개수를 말한다. 이때, 두 도시를 연결하는 도로는 하나로 count한다.

maximal network rank는 두 도시 쌍중 가장 network rank 합이 높은 것을 의미한다. 도시 개수와 road 정보가 주어질때 maximal network rank 반환하기

• Input
  도시 개수, road 정보
• Output
  maximal network rank

예제

풀이

각 노드에 대해 다음을 구한 후 max를 계속 갱신해나가는 식으로 풀었다.
1. 인접한 것들에 대한 ranksum
2. 인접하지 않은 것들에 대한 ranksum

public class Solution {
    public int MaximalNetworkRank(int n, int[][] roads) {
        List<List<int>> adjList = new List<List<int>>();
        List<int> rankList = new List<int>();
        // 인접 리스트 정보 초기화
        for (int i = 0; i < n; i++) adjList.Add(new List<int>());
        for (int i = 0; i < roads.Length; i++)
        {
            adjList[roads[i][0]].Add(roads[i][1]);
            adjList[roads[i][1]].Add(roads[i][0]);
        }
        // rank 리스트 생성 (각 노드에 대해 인접한 것들 개수 담은 리스트)
        for (int i = 0; i < n; i++)
        {
            rankList.Add(adjList[i].Count);
        }

        int maxRank = 0;

        for (int i = 0; i < n; i++)
        {
            bool[] visited = new bool[n]; // 인접하지 않은 노드 알기 위함
            visited[i] = true;
            maxRank = Math.Max(maxRank, GetMaxRank(i, adjList, rankList, visited));
        }

        return maxRank;
    }

    private int GetMaxRank(int node, List<List<int>> adjList, List<int> rankList, bool[] visited)
    {
        int maxRank = 0;
        // 인접한 것들에 대해 maxRank 계산
        for (int i = 0; i < adjList[node].Count; i++)
        {
            visited[adjList[node][i]] = true;
            int currRank = rankList[node] + rankList[adjList[node][i]] - 1;
            maxRank = Math.Max(maxRank, currRank);
        }
        // 인접하지 않은 것들에 대해 maxRank 계산
        for (int i = 0; i < visited.Length; i++)
        {
            if (!visited[i])
            {
                visited[i] = true;
                int currRank = rankList[node] + rankList[i];
                maxRank = Math.Max(maxRank, currRank);
            }
        }

        return maxRank;
    }
}

결과