Maximal Network Rank

순수 그래프 문제를 풀어보았다. 사실 이런 유형을 보면은 당연히 그래프 탐색 알고리즘이 생각나지만 아니었단거에 놀랐다. 서로 연결된 그래프가 주어졌을때 두 노드가 서로 연결하고 있는 간선(edge) 의 최대치를 반환하면 되는 문제이다.

첫번째 예시같은경우 0번째 노드는 1 과 3을 연결하고 있고
1번째 노드는 0, 2, 3을 연결하고 있지만, 1 과 0은 서로 공유하기 때문에 숫자는 하나로 계산된다. 그러므로 0과 1을 선택했을때 두 노드가 가지고 있는 최대 간선은 4가지이다.

처음 문제를 접근 했던거는 0부터 dfs 를 적용해서 각 노드가 연결하고 있는 최대치를 구하는것이었다. 0노드는 2개, 1노드도 2개 (0은 이미 visited 했기때문) 그러나 이 문제는 임의에 두 노드를 선택해서 두 노드의 최대치를 구하는 것이기 때문에 위와 같은 dfs 접근은 공유되는 간선을 구분해내기 어렵기 때문에 좋은 방법이 아니었다.

문제를 풀면서 이거 DFS 나 BFS 가 적용되지 않을 수도 있지않을까..? 싶었는데 역시 맞았다.

정말 순수하게 그래프 문제였고 답을 조금 참고하며 금방 이해 했다. set 를 이용하여 각 노드가 연결하고 있는 이웃들을 저장한 후에 완전 탐색으로 for 룹을 두번 돌리면서 모든 노드와 비교했다.

솔직히 어디까지 생각했냐면 0~n 까지의 nC2 조합을 모두 만들어서 DFS 혹은 BFS 를 돌릴까 생각했지만 이게 훨씬 나았다.

class Solution {
public:
    int maximalNetworkRank(int n, vector<vector<int>>& roads) {
        map<int,set<int>> adj; 
        int max_depth = INT_MIN; 
        for(vector<int>& v : roads){
            adj[v[0]].insert(v[1]); 
            adj[v[1]].insert(v[0]); 
        }
    
        for(int i = 0; i < n; i++){
            for(int j = i+1; j < n; j++){
                int calculate = adj[i].size() + adj[j].size(); 
                if(adj[i].count(j)) calculate--; 
                max_depth = max(max_depth,calculate); 
            }
        }
        
        return max_depth; 
    }
};

배운점:
1. 복잡하게 생각하지 않기
2. 순수 그래프 문제 풀기