자바스크립트 코딩테스트 강좌, 연결 요소의 개수 구하기

문제 설명

주어진 무방향 그래프의 연결 요소의 개수를 구하는 문제입니다. 무방향 그래프는 정점(v)과 간선(e)으로 구성되며, 정점 간의 연결성을 나타냅니다. 즉, 두 정점 사이에 간선이 있을 때, 이 두 정점은 서로 직접 연결되어 있습니다. 그래프의 연결 요소는 더 이상 연결할 수 없는 정점들의 집합을 의미합니다. 이 문제에서는 여러 개의 집합이 존재할 수 있으며, 각 집합의 정점들은 서로 도달 가능하지만 다른 집합의 정점들과는 도달할 수 없습니다. 예를 들어, 다음과 같은 그래프를 고려해 보겠습니다.

          0 --- 1     3 --- 4
                |
                2
        

이 그래프에서 연결 요소는 두 개입니다: {0, 1, 2}와 {3, 4}. 따라서 연결 요소의 개수는 2입니다.

입력 형식

함수는 두 개의 매개변수를 받습니다:

• n: 정점의 개수 (0 ≤ n ≤ 1000)
• edges: 간선의 리스트, 각 간선은 정점의 번호로 이루어진 배열입니다. 예: [[0,1], [1,2], [3,4]]

출력 형식

연결 요소의 개수를 반환합니다.

예제

          입력: n = 5, edges = [[0,1], [1,2], [3,4]]
          출력: 2

          입력: n = 6, edges = [[0,1], [0,2], [1,3]]
          출력: 3
        

해결 방법

연결 요소의 개수를 구하기 위해 DFS(Depth First Search) 알고리즘을 사용할 수 있습니다. DFS는 한 정점에서 시작하여 인접한 정점으로 깊이 들어가며 방문하지 않은 정점을 탐색하는 방식입니다. 이 알고리즘을 활용하여 그래프를 탐색하면서 연결 요소를 구별할 수 있습니다. 이를 구현하기 위한 단계는 다음과 같습니다:

1. 그래프 생성: 정점과 간선의 정보를 바탕으로 그래프를 인접 리스트 형태로 변환합니다.
2. 방문 배열 만들기: 각 정점이 방문되었는지를 체크하기 위한 배열을 생성합니다.
3. DFS 구현: 재귀 함수를 사용하여 DFS 탐색을 구현하고, 각 정점을 방문할 때 해당 정점에 연결된 모든 정점을 확인합니다.
4. 연결 요소 카운트: 모든 정점을 방문하고, 새로운 시작 정점이 발견될 때마다 연결 요소의 개수를 증가시킵니다.

자바스크립트 코드 구현

            
            function countConnectedComponents(n, edges) {
                // 그래프를 인접 리스트 형태로 변환
                const graph = Array.from({length: n}, () => []);
                edges.forEach(([u, v]) => {
                    graph[u].push(v);
                    graph[v].push(u);
                });

                const visited = new Array(n).fill(false);
                let count = 0;

                function dfs(node) {
                    visited[node] = true;
                    for (const neighbor of graph[node]) {
                        if (!visited[neighbor]) {
                            dfs(neighbor);
                        }
                    }
                }

                for (let i = 0; i < n; i++) {
                    if (!visited[i]) {
                        dfs(i);
                        count++; // 새로운 연결 요소를 발견할 때마다 증가
                    }
                }

                return count;
            }

            // 예제 실행
            console.log(countConnectedComponents(5, [[0,1],[1,2],[3,4]])); // 출력: 2
            console.log(countConnectedComponents(6, [[0,1],[0,2],[1,3]])); // 출력: 3
            
        

복잡도 분석

이 알고리즘의 시간 복잡도는 O(V + E)입니다. 여기서 V는 정점의 수, E는 간선의 수입니다. 그래프의 모든 정점과 간선을 방문하기 때문입니다. 공간 복잡도 또한 O(V)로, 방문 배열과 그래프를 저장하기 위해 사용되는 공간을 포함합니다.

마무리

이번 강좌에서는 자바스크립트를 이용하여 연결 요소의 개수를 구하는 알고리즘을 구현해 보았습니다. 그래프 이론은 코딩 테스트에서 매우 중요한 주제이며, 이와 관련된 문제들을 충분히 연습하여 실력을 쌓는 것이 중요합니다. 다양한 예제를 통해 이해를 깊이 하고, 자신만의 알고리즘적 사고를 기르는 데 도움이 되기를 바랍니다.