Blind 75 Must do Leetcode: Number of Connected Components in an Undirected Graph

2024년에도 리트코드를 꾸준히 풀어보려고 한다. 데일리 챌린지도 습관을 유지하기에 좋은 문제들이지만, 핵심적인 문제들부터 풀어보는 게 좋을 것 같아서 Blind 75 문제 셋을 다시 풀어보고자 한다. 풀면서 특정 주제에 대해서 복습도 하고 다양한 유형도 익혀보면 더 체계적으로 배울 수 있을 것 같아서다. 

https://leetcode.com/problems/number-of-connected-components-in-an-undirected-graph

LeetCode - The World's Leading Online Programming Learning Platform

오늘의 문제는 Number of Connected Components in an Undirected Graph다. n개의 노드와 엣지 리스트가 주어졌을 때, 그래프에서 연결된 컴포넌트의 개수를 찾는 문제다.

문제를 풀기 위해서 먼저 그래프를 표현해야 한다. 노드와 접해있는 다른 노드를 표현하는 방법으로 adjancy matrix, adjancy list가 있는데, adjancey list가 공간, 시간면에서 효율적이기 때문에 adjancy list를 사용한다.

그리고 DFS(depth first search)를 구현해서 각 노드를 순회한다. 방문한 노드에 표시를 하면서 재귀적으로 연결된 노드를 모두 순회한다. 아직 방문하지 않은 노드에 대해서 DFS를 할 때마다 연결된 모든 노드에 표시를 하게 된다.

그렇다면 연결된 컴포넌트의 수는 우리가 방문하지 않은 노드에 대해서 DFS를 실행한 횟수와 같다.

이 로직을 자바로 구현하면 다음과 같다.

class Solution {
    public int countComponents(int n, int[][] edges) {
        Map<Integer, List<Integer>> edgeMap = new HashMap<>();
        for(int[] edge : edges) {
            List<Integer> neighbors = edgeMap.getOrDefault(edge[0], new ArrayList<>());
            neighbors.add(edge[1]);
            edgeMap.put(edge[0], neighbors);
            neighbors = edgeMap.getOrDefault(edge[1], new ArrayList<>());
            neighbors.add(edge[0]);
            edgeMap.put(edge[1], neighbors);
        }
        int count = 0;
        boolean[] visited = new boolean[n];
        for(int node = 0; node < n; node++) {
            if (!visited[node]) {
                visited[node] = true;
                count++;
                dfs(edgeMap, node, visited);
            }
        }
        return count;
    }

    private void dfs(Map<Integer, List<Integer>> edgeMap, int node, boolean[] visited) {
        List<Integer> neighbors = edgeMap.getOrDefault(node, new ArrayList<>());
        for(int neighbor : neighbors) {
            if (!visited[neighbor]) {
                visited[neighbor] = true;
                dfs(edgeMap, neighbor, visited);
            }
        }
    }
}

시간 복잡도를 분석해보자. edges 배열의 크기가 E, 노드의 수를 N이라고 하자. 그래프를 표현하는 edgeMap을 생성할 때 edges 배열을 순회하면서(O(E)) 배열에 원소를 넣어주고(O(1)) 있기 때문에 O(E)가 필요하다. 

DFS는 방문하지 않은 노드에 대해서만 시작한다. 그래서 최악의 경우는 모든 노드와 모든 에지를 한 번씩 방문하는 경우이다.  따라서 DFS의 시간 복잡도는 O(N + E)이다. 그래서 최종 시간 복잡도는 O(E) + O(N + E) = O(N + E)가 된다.

공간 복잡도를 분석해보자. edgeMap은 모든 edge를 두 번씩 저장하고 있다. O(2E) = O(E).

visited 배열은 노드의 개수만큼 공간이 필요하므로 O(N).

DFS를 재귀로 구현했기 때문에 stack은 최악의 경우 O(N)이다.

따라서 최종 공간 복잡도는 O(E + N + N) = O(E + N)이 된다.