Redundant Connection

Q: Redundant Connection의 시간 복잡도는 무엇인가요?

유니온 파인드는 n 개의 간선을 한 번 순회하여 이 문제를 해결합니다. 시간 복잡도는 O(n · α(n))이며, α(n)은 실제로 최대 4이고, 공간 복잡도는 O(n)입니다. 잎을 제거하는 방법도 O(n)입니다. 매번 새로 탐색하여 각 제거를 시도하면 O(n²)의 비용이 듭니다.

보통유니온 파인드 그래프

+10

네트워크는 트리로 시작했습니다. n개의 노드가 1부터 n까지 번호가 매겨져 있고, 사이클이 없는 n-1개의 무방향 간선으로 연결되어 있었습니다. 그런 다음 직접 연결되어 있지 않은 두 노드 사이에 간선 하나를 더 추가하여, 이제 edges 목록에는 n개의 간선과 정확히 하나의 사이클이 있습니다.

간선 하나를 제거하여 나머지 n-1개의 간선이 다시 트리를 이루도록 하세요. 제거할 수 있는 간선이 여러 개라면, edges에서 가장 마지막에 나타나는 간선을 그곳에 쓰인 그대로 [a, b] 쌍으로 반환하세요.

함수

findRedundantConnection(edges: integer-2d-array) → integer-array

edgesinteger-2d-array: n개의 무방향 간선으로, 각 간선은 1부터 번호가 매겨진 노드 쌍 [a, b]입니다
반환값integer-array: edges에서 마지막에 나타나는 사이클 간선(거기에 적힌 그대로)

제약 조건

3 ≤ n ≤ 5000, 여기서 n = edges.length
edges[i] = [a, b]이며 1 ≤ a, b ≤ n이고 a ≠ b
어느 방향으로든 같은 변이 두 번 나타나지 않습니다.
간선은 n개의 모든 노드를 연결하며 정확히 하나의 사이클을 이룹니다.

예제

입력: edges = [[1, 2], [1, 3], [2, 3]]
출력: [2, 3]
설명: 세 변은 삼각형 1, 2, 3을 이루므로, 그중 어느 하나를 제거해도 트리가 남습니다. [2, 3]은 목록에서 마지막에 옵니다.

입력: edges = [[1, 2], [2, 3], [3, 4], [1, 4], [1, 5]]
출력: [1, 4]
설명: 순환은 1, 2, 3, 4, 1입니다. 간선 [1, 5]은 순환에 포함되지 않습니다. 이 간선을 제거하면 노드 5가 분리됩니다. 네 개의 순환 간선 중 [1, 4]가 마지막에 나타납니다.

후속 질문

간선에 방향이 있고 원래 그래프가 루트 트리라면, 추가 간선으로 인해 한 노드에 부모가 둘 생길 때 어떤 간선을 제거해야 할까요?

힌트

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

3개 중 0개 열림

풀이

간선을 제거했을 때 트리가 되는 경우는 그 간선이 그래프의 유일한 사이클에 있을 때뿐이므로, 답은 목록에서 가장 마지막에 나오는 사이클 간선입니다. 유니온 파인드로 한 번의 순회만으로 찾을 수 있습니다. 간선을 순서대로 추가하고, 양 끝점이 이미 연결된 첫 번째 간선이 답입니다.

각 간선을 제거해 보세요. 마지막 간선부터 시작하세요.

정답이지만 가장 큰 테스트에서는 끝나지 않음

핵심 아이디어

간선 하나를 제거하고 나머지 n-1개의 간선이 트리를 이루는지 확인하세요. 노드가 n개이고 간선이 n-1개일 때, 노드 1에서 탐색을 시작해 n개의 노드에 모두 도달하면 트리를 이룹니다. 목록의 끝에서부터 간선을 시도하면, 조건을 처음 만족하는 제거가 가장 뒤에 있는 간선입니다. 인접 리스트에 각 간선의 인덱스를 저장하면, 아무것도 다시 만들지 않고 탐색 중 제거된 간선을 건너뛸 수 있습니다.

시도할 때마다 O(n) 전체 탐색을 수행하며, 시도 횟수는 n번일 수 있습니다. n = 5000일 때 최대 2.5 × 10^7번의 연산이 발생합니다.

알고리즘

각 이웃에 대해 그 이웃으로 이어지는 간선의 인덱스를 유지하는 인접 리스트를 만드세요.
마지막 인덱스부터 0까지 skip에 대해, 노드 1에서 탐색을 시작하고 인덱스가 skip인 간선은 무시하세요.
탐색이 도달하는 노드 수를 세세요.
모든 n개 노드에 도달하면 edges[skip]을 반환하세요.

def findRedundantConnection(edges):
    n = len(edges)
    # graph[x] holds (neighbour, index of the edge) for every edge at node x.
    graph = [[] for _ in range(n + 1)]
    for i, (u, v) in enumerate(edges):
        graph[u].append((v, i))
        graph[v].append((u, i))
    # Try leaving out each edge, the last one first.
    for skip in range(n - 1, -1, -1):
        # Without edge skip, can node 1 still reach all n nodes?
        seen = [False] * (n + 1)
        seen[1] = True
        stack = [1]
        reached = 1
        while stack:
            node = stack.pop()
            for nxt, i in graph[node]:
                if i != skip and not seen[nxt]:
                    seen[nxt] = True
                    reached += 1
                    stack.append(nxt)
        # n-1 edges that connect n nodes form a tree.
        if reached == n:
            return edges[skip]
    return []

잎을 벗겨 내세요

핵심 아이디어

리프, 즉 간선이 하나인 노드는 사이클에 있을 수 없습니다. 사이클은 각 노드로 들어오는 간선과 나가는 간선을 갖기 때문입니다. 리프를 제거하면 이웃 노드가 리프가 될 수 있으므로, 더 이상 남은 리프가 없을 때까지 계속 제거합니다. 사이클의 각 노드에는 사이클 간선이 두 개씩 남으므로, 남는 것은 정확히 사이클입니다. 두 번째 예시에서는 노드 5를 제거하고, 노드 1에는 간선 두 개가 남으며, 노드 1부터 4까지가 남습니다.

남은 두 노드 사이의 간선은 모두 사이클 간선입니다. 사이클 노드 사이에 두 번째 연결이 있으면 두 번째 사이클이 만들어지기 때문입니다. 따라서 edges를 끝에서부터 확인하고 양 끝이 모두 남아 있는 첫 번째 간선을 반환합니다.

알고리즘

인접 리스트를 만들고 모든 노드의 차수를 셉니다.
차수가 1인 모든 노드를 스택에 넣습니다.
리프를 꺼내 차수를 0으로 설정하고, 남은 이웃 노드의 차수를 낮춥니다. 그 노드의 차수가 1로 떨어지면 스택에 넣습니다.
스택이 비면 차수가 0보다 큰 노드들이 사이클을 이룹니다.
edges를 끝에서부터 살펴보고, 양쪽 끝 노드가 모두 남아 있는 첫 번째 간선을 반환합니다.

def findRedundantConnection(edges):
    n = len(edges)
    graph = [[] for _ in range(n + 1)]
    degree = [0] * (n + 1)
    for u, v in edges:
        graph[u].append(v)
        graph[v].append(u)
        degree[u] += 1
        degree[v] += 1
    # A node with one edge cannot lie on the cycle. Remove it, and repeat.
    stack = [x for x in range(1, n + 1) if degree[x] == 1]
    while stack:
        leaf = stack.pop()
        degree[leaf] = 0
        for nxt in graph[leaf]:
            if degree[nxt] > 0:
                degree[nxt] -= 1
                if degree[nxt] == 1:
                    stack.append(nxt)
    # Only the cycle is left. Its edge that comes last in the list is the answer.
    for u, v in reversed(edges):
        if degree[u] > 0 and degree[v] > 0:
            return [u, v]
    return []

유니온 파인드: 사이클을 완성하는 첫 번째 간선

핵심 아이디어

간선들을 목록의 순서대로 추가하고 어떤 노드들이 연결되어 있는지 추적합니다. 사이클이 닫힐 때까지 각 간선은 경로가 없는 두 조각을 연결합니다. 양 끝이 이미 연결되어 있는 첫 번째 간선이 사이클을 닫습니다. 사이클의 다른 간선들은 그보다 먼저 추가되었으므로, 이 간선이 사이클을 이루는 간선 중 마지막에 나타납니다. 두 번째 예시에서 [1, 4]는 노드 1과 4가 이미 연결되어 있음을 찾아내며, [1, 5]는 읽히지 않습니다.

유니온-파인드는 parent라는 배열 하나를 유지합니다. 노드에서 포인터를 따라가면 해당 조각의 루트에 도달합니다. 작은 조각을 큰 조각 아래에 붙이고, find를 수행할 때 노드가 조부모를 가리키도록 하면 체인을 짧게 유지할 수 있습니다. 따라서 각 연산의 상각 비용은 O(α(n))이며, α는 역 아커만 함수로 실제 입력에서는 최대 4입니다.

알고리즘

1부터 n까지 모든 노드가 자기 자신을 가리키도록 하고, parent[x] = x로 설정한 다음 크기를 1로 지정합니다.
edges를 순서대로 살펴봅니다. [u, v]에 대해 u의 루트와 v의 루트를 찾습니다.
루트가 같다면 [u, v]가 사이클을 닫습니다. 그대로 반환합니다.
그렇지 않으면 더 큰 집합이 더 작은 집합을 흡수합니다. 더 큰 집합의 루트가 더 작은 루트의 부모가 되고, 크기를 합산합니다.

def findRedundantConnection(edges):
    n = len(edges)
    parent = list(range(n + 1))  # every node starts as its own group
    size = [1] * (n + 1)

    def find(x):
        # Walk up to the root, halving the path on the way.
        while parent[x] != x:
            parent[x] = parent[parent[x]]
            x = parent[x]
        return x

    for u, v in edges:
        a, b = find(u), find(v)
        # u and v are already connected: this edge closes the cycle.
        if a == b:
            return [u, v]
        # Hang the smaller group under the larger one.
        if size[a] < size[b]:
            a, b = b, a
        parent[b] = a
        size[a] += size[b]
    return []

함정과 경계 사례

목록의 마지막 간선을 반환하는 것. 두 번째 예시에서는 [1, 5]이며, 이를 제거하면 노드 5가 끊어집니다.
간선을 하나씩 제거한 뒤 앞에서부터 탐색하는 것. 그러면 가장 먼저 나오는 사이클 간선인 두 번째 예시의 [1, 2]가 반환됩니다.
쌍을 정렬하거나 순서를 뒤집는 것. 목록에 [3, 1]이 있으면 [1, 3]이 아니라 [3, 1]을 반환해야 합니다.
노드 0부터 n-1까지 배열의 크기를 지정하는 것. 노드 번호는 1부터 시작하므로 노드 n에는 n+1개의 슬롯이 필요합니다.
사이클을 따라 재귀적으로 탐색하는 것. 5000개 노드를 모두 지날 수 있는데, 이는 Python의 기본 재귀 제한의 5배이므로 find에서 명시적 스택과 루프를 사용하세요.

자주 묻는 질문3

Redundant Connection의 시간 복잡도는 무엇인가요?

유니온 파인드는 n개의 간선을 한 번 순회하여 이 문제를 해결합니다. 시간 복잡도는 O(n · α(n))이며, α(n)은 실제로 최대 4이고, 공간 복잡도는 O(n)입니다. 잎을 제거하는 방법도 O(n)입니다. 매번 새로 탐색하여 각 제거를 시도하면 O(n²)의 비용이 듭니다.

어떤 간선을 제거해야 트리가 남을까요?

사이클 위의 간선만 해당합니다. 각 간선은 사이클의 나머지 부분을 통해 양 끝점 사이를 잇는 두 번째 경로가 있으므로, 해당 간선을 제거해도 그래프는 연결된 상태로 유지됩니다. 다른 간선은 그래프의 두 부분을 잇는 유일한 연결이므로, 이를 제거하면 그래프가 분리됩니다.

중복 연결 문제를 DFS로 해결할 수 있나요?

네. 각 간선을 추가하기 전에 한쪽 끝에서 지금까지 추가된 간선들을 따라 탐색합니다. 반대쪽 끝에 이미 도달할 수 있는 첫 번째 간선이 답입니다. 간선마다 O(n), 전체적으로 O(n²)의 시간이 걸리며, union-find는 같은 질문에 거의 상수 시간으로 답합니다.

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

테스트 #1

테스트 #2

인자

edges = [[1, 2], [1, 3], [2, 3]]

예상 출력

[2, 3]

Redundant Connection

함수

제약 조건

예제

힌트

풀이

각 간선을 제거해 보세요. 마지막 간선부터 시작하세요.

잎을 벗겨 내세요

유니온 파인드: 사이클을 완성하는 첫 번째 간선

함정과 경계 사례

자주 묻는 질문3

비슷한 문제