Number of Provinces

Q: Number of Provinces의 시간 복잡도는 얼마인가요?

그래프 탐색 또는 유니온 파인드를 사용하면 O(n²)입니다. 두 방법 모두 n × n 행렬의 모든 항목을 한 번씩 읽기 때문입니다. 유니온 파인드는 역 아커만 함수인 α(n)만큼의 계수가 추가되며, 실제로는 최대 4입니다. 추가 공간은 O(n)입니다.

Q: Number of Provinces에는 DFS, BFS 또는 union-find 중 무엇을 사용해야 할까요?

세 가지 모두 O(n²) 시간에 같은 개수를 반환합니다. DFS나 BFS가 작성하기 가장 간단합니다. 각 답변을 거의 상수 시간에 구할 수 있으므로, “이 두 도시는 같은 주에 속하는가?”와 같은 질문에도 많이 답해야 한다면 유니온 파인드가 더 적합한 도구입니다.

Q: Number of Provinces와 Number of Islands는 어떻게 다른가요?

둘 다 연결 요소의 개수를 셉니다. Number of Islands에서는 그래프가 격자이고, 각 칸에는 최대 네 개의 이웃이 있으며, 작업량은 O(rows × cols)입니다. 여기서 그래프는 인접 행렬입니다. 어떤 도시든 다른 어느 도시와 연결될 수 있으며, 한 도시의 이웃을 나열하려면 n 개의 항목으로 이루어진 전체 행을 읽어야 합니다.

보통유니온 파인드 그래프

+10

n개의 도시가 있으며, 각 도시에는 0부터 n-1까지 번호가 매겨져 있습니다. isConnected[i][j]는 도로가 도시 i와 도시 j를 직접 연결하면 1이고, 그렇지 않으면 0입니다. 도로는 양방향으로 통행할 수 있으므로 행렬은 대칭이며, 모든 도시는 자기 자신과 연결되어 있습니다.

주는 다른 도시를 거치거나 직접 서로 도달할 수 있고, 그룹 밖으로 이어지는 도로가 없는 도시들의 집합입니다. 주의 개수를 반환하세요.

함수

findCircleNum(isConnected: integer-2d-array) → integer

isConnectedinteger-2d-array: n × n 행렬로, 도로가 두 도시를 직접 연결하는 곳에는 1
반환값integer: 주의 개수

제약 조건

1 ≤ n ≤ 150, 여기서 n = isConnected.length
isConnected[i].length = n
isConnected[i][j]는 0 또는 1입니다
isConnected[i][i] = 1
isConnected[i][j] = isConnected[j][i]

예제

입력: isConnected = [[1, 0, 0, 1], [0, 1, 1, 0], [0, 1, 1, 0], [1, 0, 0, 1]]
출력: 2
설명: 도시 0은 도시 3으로 가는 도로가 있고, 도시 1은 도시 2로 가는 도로가 있습니다. 두 쌍 사이를 잇는 도로는 없으므로, 주는 2개입니다.

후속 질문

이제 각 도로는 정해진 날에 개통됩니다. 모든 도시가 하나의 주에 속하게 되는 첫날을 찾을 수 있나요?

힌트

하나씩 열어 보세요. 열 때마다 조금 더 알려 줍니다.

3개 중 0개 열림

풀이

행렬은 무방향 그래프를 나타냅니다. 도시는 노드이고 각 1은 간선입니다. 하나의 주(province)는 연결 요소이며, 세 번째 도시가 두 도시를 모두 연결한다면 두 도시 사이의 0은 두 도시를 분리하지 않습니다. 방문하지 않은 각 도시에서 탐색을 수행하거나 모든 간선에 대해 유니온-파인드를 사용하면 O(n²)에 연결 요소의 개수를 셀 수 있습니다.

방문하지 않은 모든 도시에서 시작하는 깊이 우선 탐색

핵심 아이디어

표시되지 않은 도시는 이미 개수를 센 주에 속할 수 없습니다. 각 탐색이 주 전체를 표시하기 때문입니다. 따라서 그 도시는 새로운 주를 시작합니다. 탐색은 행렬의 행을 따라 진행됩니다. 두 번째 예시에서 도시 0에서 시작한 탐색은 도시 1에 도달하고, 이어서 도시 1의 행을 통해 도시 2에 도달합니다. 하지만 행 0에는 도시 2에 대해 0이 있습니다.

각 도시는 한 번씩 스택에서 꺼내지고 n개의 항목으로 이루어진 행을 읽으므로, 행렬을 한 번 읽습니다. 시간 복잡도는 O(n²)입니다. 표시와 스택은 최대 n개의 도시를 담으므로 추가 공간 복잡도는 O(n)입니다.

알고리즘

각 도시에 대해 방문 여부 플래그를 만들고 개수를 0으로 설정합니다.
도시를 순서대로 확인하고 이미 방문한 도시는 건너뜁니다.
방문하지 않은 도시를 만나면 개수에 1을 더하고, 해당 도시를 방문 표시한 다음 스택에 넣습니다.
스택에 도시가 있는 동안 하나를 꺼내고, 해당 도시의 행에서 값이 1이고 아직 방문하지 않은 도시를 모두 스택에 넣으면서 방문 표시합니다.
개수를 반환합니다.

def findCircleNum(isConnected):
    n = len(isConnected)
    seen = [False] * n
    provinces = 0
    for start in range(n):
        if seen[start]:
            continue
        # Nobody reached this city from an earlier province, so it starts a new one.
        provinces += 1
        seen[start] = True
        stack = [start]
        while stack:
            city = stack.pop()
            row = isConnected[city]
            for other in range(n):
                # Mark a city when you push it, so it is never pushed twice.
                if row[other] == 1 and not seen[other]:
                    seen[other] = True
                    stack.append(other)
    return provinces

경로 압축 및 랭크 기반 합집합을 사용하는 유니온-파인드

핵심 아이디어

n개의 주를 만들고, 처음에는 각 도시에 하나씩 배정합니다. 대각선 위의 1은 두 도시가 같은 그룹에 속한다는 뜻입니다. 두 도시의 그룹이 다르면 두 그룹을 합치고 개수를 1 줄입니다. 두 번째 예시에서는 개수가 5에서 시작하고, (0, 1)은 도시 0과 1을 합치며, (1, 2)는 도시 2를 두 도시의 그룹에 포함하므로, 주는 3개가 남습니다.

유니온-파인드는 각 그룹을 트리로 저장합니다. parent[c]는 한 단계 위를 가리키며, find가 두 도시를 따라 올라가 같은 루트에 도달하면 두 도시는 같은 그룹에 속합니다. 아무런 최적화를 하지 않으면 병합으로 긴 경로 하나가 만들어질 수 있고, 그러면 모든 find가 O(n) 단계만큼 경로를 따라가야 합니다. 랭크에 따른 합치기는 더 짧은 트리를 더 긴 트리 아래에 붙이므로, 어떤 경로도 log n보다 길어지지 않습니다. 경로 압축은 find가 지나간 모든 도시가 루트를 바로 가리키도록 합니다. 이 두 기법을 함께 사용하면 각 find의 분할 상환 시간은 O(α(n))이 되고, α(n)은 실제로 최대 4입니다.

알고리즘

모든 도시에 대해 parent[c] = c와 rank[c] = 0으로 설정하고, 개수는 n으로 설정합니다.
isConnected[i][j] = 1인 모든 i < j 쌍에 대해 i와 j의 루트를 찾습니다.
find에서는 루트까지 올라간 다음, 경로를 다시 따라가면서 경로에 있는 각 도시가 루트를 가리키도록 합니다.
루트가 서로 다르면 순위가 낮은 루트를 다른 루트 아래에 연결하고, 순위가 같으면 순위에 1을 더한 다음 개수에서 1을 뺍니다.
개수를 반환합니다.

def findCircleNum(isConnected):
    n = len(isConnected)
    parent = list(range(n))
    rank = [0] * n

    def find(city):
        root = city
        while parent[root] != root:
            root = parent[root]
        # Path compression: point every city on the way straight at the root.
        while parent[city] != root:
            up = parent[city]
            parent[city] = root
            city = up
        return root

    provinces = n
    for i in range(n):
        for j in range(i + 1, n):  # the matrix is symmetric, so the upper half is enough
            if isConnected[i][j] == 1:
                a, b = find(i), find(j)
                if a == b:
                    continue
                # Union by rank: hang the shorter tree under the taller one.
                if rank[a] < rank[b]:
                    a, b = b, a
                parent[b] = a
                if rank[a] == rank[b]:
                    rank[a] += 1
                # Two provinces just became one.
                provinces -= 1
    return provinces

함정과 경계 사례

직접 연결된 도로만 믿는 것. 두 번째 예제의 도시 0과 2 사이에는 0이 있지만 여전히 같은 주에 속합니다.
1의 개수를 세고 2로 나누는 것. 서로 모두 연결된 세 도시에는 도로가 세 개 있고 주는 하나입니다.
유니온 파인드에서 두 루트가 서로 다를 때만이 아니라 모든 1마다 개수를 줄이는 것.
parent[i]와 parent[j]를 비교하는 것. 한 그룹에 속한 두 도시는 한 도시가 더 깊은 곳에 있으면 부모가 다를 수 있습니다. find(i)와 find(j)를 비교하세요.
parent[j] = find(i)처럼 도시 j 자체를 연결하는 것. j가 이미 그룹에 속해 있었다면, 그 그룹의 나머지 도시는 병합에서 제외됩니다.

자주 묻는 질문3

Number of Provinces의 시간 복잡도는 얼마인가요?

그래프 탐색 또는 유니온 파인드를 사용하면 O(n²)입니다. 두 방법 모두 n × n 행렬의 모든 항목을 한 번씩 읽기 때문입니다. 유니온 파인드는 역 아커만 함수인 α(n)만큼의 계수가 추가되며, 실제로는 최대 4입니다. 추가 공간은 O(n)입니다.

Number of Provinces에는 DFS, BFS 또는 union-find 중 무엇을 사용해야 할까요?

세 가지 모두 O(n²) 시간에 같은 개수를 반환합니다. DFS나 BFS가 작성하기 가장 간단합니다. 각 답변을 거의 상수 시간에 구할 수 있으므로, “이 두 도시는 같은 주에 속하는가?”와 같은 질문에도 많이 답해야 한다면 유니온 파인드가 더 적합한 도구입니다.

Number of Provinces와 Number of Islands는 어떻게 다른가요?

둘 다 연결 요소의 개수를 셉니다. Number of Islands에서는 그래프가 격자이고, 각 칸에는 최대 네 개의 이웃이 있으며, 작업량은 O(rows × cols)입니다. 여기서 그래프는 인접 행렬입니다. 어떤 도시든 다른 어느 도시와 연결될 수 있으며, 한 도시의 이웃을 나열하려면 n개의 항목으로 이루어진 전체 행을 읽어야 합니다.

def findCircleNum(isConnected):
    # 여기에 코드를 작성하세요

테스트 #1

테스트 #2

인자

isConnected = [[1, 0, 0, 1], [0, 1, 1, 0], [0, 1, 1, 0], [1, 0, 0, 1]]

예상 출력