파이썬으로 친구 관계 그래프에서 친구 그룹 수 찾기 – DFS 연결 요소 풀이

문제 이해하기

친구 관계를 나타내는 리스트가 있다고 가정해 보겠습니다. 여기서 friends[i]는 사람 i와 친구인 사람들의 목록입니다. 친구 관계는 양방향이며, 각 사람은 자기 자신과도 친구로 간주합니다. 두 사람 사이에 서로 다른 친구들을 거쳐 이어지는 경로가 존재한다면, 그 두 사람은 같은 친구 그룹에 속하게 됩니다. 우리가 구해야 할 값은 전체 친구 그룹의 개수입니다.

예를 들어 입력이 friends = [[0, 1, 5], [1, 0], [2], [3, 4], [4, 3], [5, 0]]이라면 출력은 3이 됩니다. 세 개의 친구 그룹은 다음과 같습니다.

• 그룹 1: {0, 1, 5} — 0번, 1번, 5번이 서로 연결됨
• 그룹 2: {2} — 혼자만 있는 그룹
• 그룹 3: {3, 4} — 3번과 4번이 서로 연결됨

접근 방법: 깊이 우선 탐색(DFS)

이 문제는 그래프 이론에서 말하는 연결 요소(Connected Component)의 개수를 세는 것과 동일합니다. 아직 방문하지 않은 노드를 발견할 때마다 DFS를 시작해 해당 노드와 연결된 모든 노드를 방문 처리하고, 그때마다 그룹 수를 하나씩 늘려가면 됩니다.

알고리즘 단계

1. nodes := friends 리스트의 크기
2. visited := nodes 크기만큼 False로 초기화된 방문 배열 생성
3. ans := 0 (친구 그룹 개수)
4. dfs(vertex) 함수 정의: 현재 정점을 방문 처리하고, 인접한 친구 중 아직 방문하지 않은 정점에 대해 재귀적으로 dfs를 호출
5. 메인 루프에서 0부터 nodes-1까지 반복하며, 방문하지 않은 정점을 만나면 dfs를 실행하고 ans를 1 증가
6. ans 반환

구현 예제

class Solution:
    def solve(self, friends):
        nodes = len(friends)
        visited = [False for _ in range(nodes)]
        ans = 0

        def dfs(vertex):
            visited[vertex] = True
            for nei in friends[vertex]:
                if not visited[nei]:
                    dfs(nei)

        for i in range(nodes):
            if not visited[i]:
                dfs(i)
                ans += 1

        return ans

ob = Solution()
friends = [[0, 1, 5], [1, 0], [2], [3, 4], [4, 3], [5, 0]]
print(ob.solve(friends))

입력

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

출력

3

시간 및 공간 복잡도

각 노드와 간선을 최대 한 번씩만 방문하므로 시간 복잡도는 O(N + E)입니다. 여기서 N은 사람 수, E는 친구 관계(간선)의 수입니다. 공간 복잡도는 방문 배열과 재귀 호출 스택 때문에 O(N)입니다.

마무리

DFS 대신 BFS(너비 우선 탐색)나 유니온-파인드(Union-Find) 자료구조를 사용해도 동일한 결과를 얻을 수 있습니다. 특히 입력 크기가 매우 커서 재귀 깊이 제한에 걸릴 가능성이 있다면, 반복문 기반의 BFS나 스택을 활용한 반복적 DFS로 구현하는 것이 안전합니다.