[Python] LeetCode - 1319. Number of Operations to Make Network Connected

LeetCode 1319번 Number of Operations to Make Network Connected 문제는 그래프 탐색 관련 문제다. 난이도는 Medium이며 DFS/BFS를 통해 해결할 수 있다.

 

리트코드 1319번 문제 정보

알고리즘 분류

- 그래프 탐색

난이도

- Medium

 

문제 요약

• 0부터 n-1까지의 컴퓨터 n개, 그리고 컴퓨터간에 연결된 이더넷 케이블을 나타내는 connections가 주어진다.
• 케이블을 옮겨서 모든 컴퓨터가 연결되도록 하려면 최소 몇개의 케이블을 옮겨야 하는지 구하라.
  • 케이블이 모자라면 -1을 반환한다.

 

문제 풀이 과정

• 초기 상태에서 몇개의 그룹이 생기는지 구한다.
• 그룹들을 잇기 위해 필요한 케이블 개수 (그룹 수) - 1을 반환한다.
• 전체 케이블 개수가 필요한 케이블 개수보다 적으면 -1을 반환한다.

코드 (파이썬)

class Solution:
    def makeConnected(self, n: int, connections: List[List[int]]) -> int:
        if len(connections) < n-1:
            return -1

        adj_dict = {key: [] for key in range(n)}
        for s, d in connections:
            adj_dict[s].append(d)
            adj_dict[d].append(s)

        group_cnt = 0
        visited = [0] * n
        def dfs(here: int):
            for dest in adj_dict[here]:
                if visited[dest] == 0:
                    visited[dest] = group_cnt
                    dfs(dest)
        
        for com in range(n):
            if visited[com] == 0:
                group_cnt += 1
                visited[com] = group_cnt
                dfs(com)
        
        return group_cnt -1

• 시간복잡도: O(n+m) (m: 케이블 개수)
• 공간복잡도: O(n+m) (m: 케이블 개수)