LeetCode 547. Number of Provinces

Graph Theory 문제 1번
https://leetcode.com/problems/number-of-provinces/

나의 풀이(268ms, 5.31%)

• 간선 단위의 DFS를 작성하여, 이미 방문한 노드를 여러 번 방문하게 된다.
• 그러니까 노드 단위로 생각하면 되는데, 간선 단위로 생각해서 불필요한 호출이 많아 비효율적이다.

class Solution:
    def findCircleNum(self, isConnected: List[List[int]]) -> int:
        province = 0
        
        def dfs(i, j):
            if i > j:
                i, j = j, i
            if isConnected[i][j] == 1:
                isConnected[i][j] = 0
                for k in range(len(isConnected)):
                    dfs(i, k)
                    dfs(j, k)

        for i in range(len(isConnected)):
            for j in range(i, len(isConnected)):
                if isConnected[i][j] == 1:
                    province += 1
                    dfs(i, j)

        return province

다른 풀이1(3ms, 89.46%)

DFS + 방문 배열

class Solution:
    def findCircleNum(self, isConnected: List[List[int]]) -> int:
        n = len(isConnected)
        visited = [False] * n

        def dfs(i):
            for j in range(n):
                if isConnected[i][j] == 1 and not visited[j]:
                    visited[j] = True
                    dfs(j)

        province = 0
        for i in range(n):
            if not visited[i]:
                visited[i] = True
                dfs(i)
                province += 1
        return province

다른 풀이2(7ms, 56.95%)

BFS

class Solution:
    def findCircleNum(self, isConnected: List[List[int]]) -> int:
        n = len(isConnected)
        visited = [False] * n
        count = 0

        for i in range(n):
            if not visited[i]:
                queue = deque([i])
                while queue:
                    node = queue.popleft()
                    for j in range(n):
                        if isConnected[node][j] == 1 and not visited[j]:
                            visited[j] = True
                            queue.append(j)
                count += 1
        return count

다른 풀이3(3ms, 89.46%)

Union-Find (Disjoint Set Union)

class Solution:
    def findCircleNum(self, isConnected: List[List[int]]) -> int:
        parent = list(range(len(isConnected)))

        def find(x):
            if parent[x] != x:
                parent[x] = find(parent[x])
            return parent[x]

        def union(x, y):
            rootX, rootY = find(x), find(y)
            if rootX != rootY:
                parent[rootX] = rootY

        for i in range(len(isConnected)):
            for j in range(i + 1, len(isConnected)):
                if isConnected[i][j] == 1:
                    union(i, j)

        return len(set(find(i) for i in range(len(isConnected))))