[2025/03/22] 2685. Count the Number of Complete Components

leetcode.com 의 dilay qeustion 을 매일 풀어보고 있습니다!

https://leetcode.com/problems/count-the-number-of-complete-components/description/?envType=daily-question&envId=2025-03-22

1. 문제 소개

## Problem Description

You are given an integer `n`. 
There is an **undirected** graph with `n` vertices, numbered from `0` to `n - 1`. 
You are given a 2D integer array `edges` where `edges[i] = [ai, bi]` 
denotes that there exists an **undirected** edge connecting vertices `ai` and `bi`.

Return *the number of **complete connected components** of the graph*.

A **connected component** is a subgraph of a graph in which 
there exists a path between any two vertices, 
and no vertex of the subgraph shares an edge with a vertex outside of the subgraph.

A connected component is said to be **complete** 
if there exists an edge between every pair of its vertices.

간단하게 각 정점의 연결선(간선) 과 노드 수가 주어졌을 때,
완벽한(형태) 비연결 그래프의 수를 구하라는 문제입니다.
자세한 지문은 링크로 확인해주세요

2. 접근 방법 (필요 개념) 🤔

이 문제를 해결하기 위해서는 두 가지 핵심 개념을 이해해야 합니다:

1. 그래프에서 연결된 컴포넌트를 어떻게 찾을 것인가?
2. 찾은 컴포넌트가 완전(complete) 한지 어떻게 판단할 것인가?

2.1 연결 여부 판단하기

그래프에서 연결된 컴포넌트란 무엇일까요? 쉽게 말해 '서로 이어진 정점들의 집합'이라고 생각하면 됩니다.
예를 들어, 다음과 같은 그래프가 있다고 상상해볼까요?

0 --- 1 --- 2     3 --- 4     5

이 그래프에는 세 개의 연결 컴포넌트가 있습니다:

• [0, 1, 2]
• [3, 4]
• [5]

이러한 연결 컴포넌트를 찾기 위해서는 적절한 자료구조와 알고리즘이 필요합니다.

2.1.1 비연결 그래프에 알맞은 자료 구조 소개 📊

인접 리스트(Adjacency List)

인접 리스트는 각 정점마다 연결된 정점들의 목록을 저장하는 자료구조입니다. 마치 친구 목록처럼 생각하면 쉽습니다! 🧑‍🤝‍🧑

예를 들어, 위 그래프를 인접 리스트로 표현하면:

0: [1]
1: [0, 2]
2: [1]
3: [4]
4: [3]
5: []

인접 리스트의 장점은:

• 메모리 효율성: 연결된 정점만 저장하므로 공간을 절약합니다.
• 조회 효율성: edges의 [0,2], [2,0] 같은 순서에 구애받지 않고, 연결된 노드를 빠르게 확인할 수 있습니다.
• 그래프 탐색에 최적화: DFS, BFS 같은 알고리즘에 매우 효율적입니다. 구현하기 편한 것도 매우 중요하니까요!

2.1.2 DFS(깊이 우선 탐색) 🚀

DFS는 그래프를 탐색하는 가장 기본적인 알고리즘 중 하나입니다. 미로를 탐험하는 것처럼, 한 길을 끝까지 따라가보고 막히면 되돌아와 다른 길을 시도하는 방식이죠!

DFS를 사용하면:

1. 시작 정점에서 출발해 방문하지 않은 인접 정점으로 계속 이동합니다.
2. 더 이상 방문할 정점이 없으면 이전 정점으로 돌아갑니다.
3. 모든 정점을 방문할 때까지 이 과정을 반복합니다.

이 과정을 통해 주어진 edges 들이 컴포넌트를 구성하는 모든 정점을 찾아낼 수 있습니다! 🕸️
(그것이 완전하든 불완전하든지요!)

2.2 완성된 그래프 판단하기 ✅

이제 연결 컴포넌트를 찾았다면, 이 컴포넌트가 '완전'한지 어떻게 판단할까요?

2.2.1 그래프 이론

완전 그래프(Complete Graph)란 모든 정점 쌍 사이에 간선이 존재하는 그래프를 말합니다.
즉, 모든 정점이 다른 모든 정점과 직접 연결되어 있어야 합니다! 🌐

수학적으로 표현하면:

• n개의 정점을 가진 완전 그래프에서 각 정점은 정확히 (n-1)개의 간선을 가져야 합니다.
• 전체 간선의 수는 n×(n-1)÷2 개입니다.

예를 들어, 3개의 정점을 가진 완전 그래프는 삼각형 모양이 되고, 각 정점은 2개의 간선을 가집니다.

따라서, 우리 문제에서 완성된 그래프인지 판단하는 방법은 간단합니다:

• 컴포넌트의 크기가 n이라면, 컴포넌트 내 각 정점이 정확히 (n-1)개의 간선을 가지는지 확인하면 됩니다!

3. 코드 첨부 💻

저는 알고리즘 공부에 더불어서 go 라는 언어도 공부중이어서 go 를 사용하여 구현해보았습니다.

func countCompleteComponents(n int, edges [][]int) int {
    graph := make([][]int, n)
    for i := 0; i < n; i++ {
        graph[i] = make([]int, 0)
    }

    for _, edge := range edges {
        a, b := edge[0], edge[1]
        graph[a] = append(graph[a], b)
        graph[b] = append(graph[b], a)
    }

    visited := make([]bool, n)
    completeCount := 0

    for i := 0; i < n; i++ {
        if !visited[i] {
            component := []int{}
            dfs(i, graph, visited, &component)

            if isComplete(component, graph) {
                completeCount++
            }
        }
    }

    return completeCount
}

func dfs(node int, graph [][]int, visited []bool, component *[]int) {
    visited[node] = true
    *component = append(*component, node)

    for _, neighbor := range graph[node] {
        if !visited[neighbor] {
            dfs(neighbor, graph, visited, component)
        }
    }
}

func isComplete(component []int, graph [][]int) bool {
    n := len(component)

    for _, node := range component {
        if len(graph[node]) != n-1 {
            return false
        }
    }

    return true
}

4. 결과 🎯

5. AI 추천 더 좋은 풀이 🌟

저는 문제는 풀었지만 더 좋은 방법이 있을지 AI 로 한번더 문제를 확인하는 편인데요. (쉽다면 암기하기!)
이 문제를 풀 수 있는 가장 효율적인 방법을 AI 에게 물어서 살펴보겠습니다:

1. 유니온-파인드(Union-Find) 활용: DFS 대신 유니온-파인드 알고리즘을 사용하면 연결 컴포넌트를 더 빠르게 찾을 수 있습니다. 특히 간선이 많은 그래프에서 유리합니다.
2. 인접 행렬 사용: 완전 그래프 판단에는 인접 행렬이 더 효율적일 수 있습니다. 두 정점 사이의 연결 여부를 O(1) 시간에 확인할 수 있기 때문입니다.

유니온 파인드(Union-Find): 그래프의 연결 관계를 빠르게 찾는 마법 🧙‍♂️

유니온 파인드(또는 '서로소 집합', Disjoint Set)는 그래프에서 연결된 요소들을 효율적으로 관리하는 알고리즘입니다.

마치 친구 관계를 추적하는 것처럼, "A와 B는 친구", "B와 C는 친구"라는 정보로부터 "A와 C도 친구군요!"라고 유추할 수 있죠!

이 알고리즘은 두 가지 핵심 연산을 제공합니다:

1. Union - 두 집합을 하나로 합치기 🤝
2. Find - 어떤 원소가 어느 집합에 속하는지 찾기 🔍

어려운 개념인 듯 하지만 실제로 구현 시에는 트리 구조를 사용하면 간단히 구현이 가능합니다! 단순한 배열로 표현이 가능한데요, 각 원소는 자신의 부모를 가리키며, 루트 노드는 자기 자신을 가리킵니다. Find 연산은 재귀적으로 부모를 따라 올라가 루트를 찾고, Union 연산은 한 트리의 루트를 다른 트리의 루트 아래에 배치합니다.
'경로 압축'을 적용(Union 구현체에서 find 결과를 캐싱) 하면 Find 연산 중 모든 노드가 바로 루트를 가리키도록 업데이트되어 후속 연산이 더욱 빨라집니다! 🚀✨

비교: Union-Find vs DFS 🥊

Union-Find와 비교하면:

Union-Find: 정점 연결 작업이 거의 상수 시간(O(α(n)) ≈ O(1))
DFS: 전체 시간 복잡도는 동일하지만 구현이 더 직관적

문제의 제약 조건(n ≤ 50)을 고려할 때, 작은 그래프에서는 속도 차이가 크지 않을 수 있지만, 더 큰 그래프에서는 이런 최적화가 중요해질 수 있습니다! 🚀
개인적으로는 이 문제에서 간선 수로 판단하는 DFS 방식은 이해하기 쉽고 정답을 내기에 충분한 방법이라고 생각되니 유니온 파인드 개념만 간단히 기억하고 넘어가도록 하겠습니다!

 

---

 

이 문제는 그래프 이론의 기본 개념을 응용하는 좋은 연습이 되었네요! 처음에는 어렵게 느껴질 수 있지만, 단계별로 생소한 개념을 하나씩 알아가다 보면 생각보다 문제가 해결하기 쉬워 질 거에요! 그래프 문제에 자신감이 생기셨나요? 다음 도전도 기대하겠습니다! 💪✨