Count Unreachable Pairs of Nodes in an Undirected Graph(leetcode, 2316)

문제 설명

서로 연결되지 않는 노드의 조합의 개수를 구하는 문제다.

문제 풀이

첫 번째 접근

일단 부분 그래프를 구성하는 노드의 개수를 알아야 겠다고 생각했다. 그 후에 각 부분 그래프의 노드의 개수를 조합으로 계산해서 풀겠다는 계획이었다.

위의 풀이는 정답은 나왔으나 시간 복잡도를 해결하지 못했다. 아마 깊이 우선탐색에 문제가 있는 건 아닐테고 그럼 조합 계산에 문제가 있다는 건데(참고로 조합 계산은 2차원 반복문을 이용했다)... 딱히 풀 수가 없어서 다른 사람의 풀이를 보니 조합을 굳이 구현하지 않고도 푼 풀이를 발견했다.

두 번째 접근

일단 각 부분 그래프의 노드의 개수를 구하는 건 내 풀이와 동일했다. 그러나 굳이 나처럼 각 그래프의 노드의 개수를 조합으로 계산하지 않았다. 대신 어느 부분 그래프의 노드 개수를 구할 때마다 바로 직전까지 구한 노드의 개수 합을 곱해서 값을 더했다.

즉, 간단하게 수식을 써보자면

정답 += (현재 부분 그래프에서 구한 노드의 개수 * 현재-1까지 구한 노드의 개수)
현재-1까지 구한 노드의 개수 = 현재 부분 그래프에서 구한 노드의 개수

이렇게 되는 것이다. 이렇게 되면 내가 처음에 구현했던 것보다 빠르게 정답을 구할 수 있다. 참고로 말하자면 현재-1까지 구한 노드의 개수는 초기값이 0이다. 왜냐하면 첫 번째 그래프를 탐색하면 현재-1까지 구한 노드의 개수는 자연스레 0이기 때문이다.

코드

Java

import java.util.*;
import java.io.*;

class Solution {
    public static List<ArrayList<Integer>> map;
    public static boolean[] visit;
    public static int count;

    public long countPairs(int n, int[][] edges) {
        map = new ArrayList<>();
        visit = new boolean[n];
        long answer = 0;
        int visited = 0;

        for(int i=0; i<n; i++){
            map.add(new ArrayList<>());
        }

        for(int[] edge : edges){
            int a = edge[0];
            int b = edge[1];

            map.get(a).add(b);
            map.get(b).add(a);
        }

        for(int i=0; i<n; i++){
            if(visit[i] == false){
                count = 0;
                dfs(i);
                answer += (long)count * visited;
                visited += count;
            }
            
        }

        return answer;

    }

    public void dfs(int node){
        visit[node] = true;
        count++;

        for(int n : map.get(node)){
            if(visit[n] == false){
                dfs(n);
            }
        }
    }

}

Python

class Solution:
    def countPairs(self, n: int, edges: List[List[int]]) -> int:
        map = [[] for _ in range(n)]
        visit = [False for _ in range(n)]
        visit_node = 0
        answer = 0
        count = 0

        for edge in edges:
            a = edge[0]
            b = edge[1]

            map[a].append(b)
            map[b].append(a)

        
        def dfs(node : int, count : int):
            visit[node] = True
            count = 1

            for n in map[node]:
                if visit[n] == False:
                    count += dfs(n, count)
            
            return count
        
        for i in range(n):
            if visit[i] == False:
                tmp = dfs(i, 0)
                answer += (tmp * visit_node)
                visit_node += tmp
        
        return answer

첫 번째 접근에서 구현한 조합

public long Combination(){
        long answer = 0;

        if(unreachable.size() == 1){
            return 0;
        }

        for(int i=0; i<unreachable.size()-1; i++){
            for(int j=i+1; j<unreachable.size(); j++){
                answer += (long)(unreachable.get(i) * unreachable.get(j));
            }
        }

        return answer;
    }