Find if Path Exists in Graph

Q: 그래프에 경로가 존재하는지 확인하는 시간 복잡도는 얼마인가요?

BFS 또는 DFS를 사용하면 노드가 n 개이고 간선이 m 개일 때 시간과 공간 복잡도는 O(n + m) 입니다. 각 노드는 한 번 방문하고 각 간선은 양쪽 끝에서 확인합니다. 크기 기준 union과 경로 절반 줄이기를 사용하는 유니온-파인드는 시간 복잡도가 O(n + m·α(n)) 이고 공간 복잡도는 O(n) 입니다. 여기서 α 는 증가 속도가 매우 느려 실제로는 작은 상수로 볼 수 있습니다.

Q: BFS에 방문 배열이 필요한 이유는 무엇인가요?

이것이 없으면 0 → 1 → 2 → 0 과 같은 순환으로 인해 검색이 끝없이 반복되고, 순환이 없더라도 여러 이웃이 있는 노드는 이웃마다 한 번씩 대기열에 추가됩니다. 각 노드를 대기열에 추가하는 순간 표시하면 각 노드가 한 번만 처리되므로 작업량이 O(n + m) 으로 제한됩니다.

Q: 유니온 파인드에서 경로 압축과 크기 기반 합치기는 어떤 역할을 하나요?

find 가 빠르게 유지되도록 트리의 깊이를 얕게 유지합니다. 크기 기준 합치기는 더 작은 트리를 더 큰 트리 아래에 연결하므로, 노드의 깊이는 해당 노드가 속한 그룹의 크기가 최소 두 배가 될 때만 증가하며, 따라서 깊이는 log n 으로 제한됩니다. 경로 압축 또는 여기서 사용된 경로 절반 나누기는 루트까지의 경로를 따라갈 때마다 그 경로를 짧게 만듭니다. 이 두 가지를 함께 사용하면 각 연산의 시간 복잡도를 α(n) 으로 낮춥니다.

쉬움그래프 유니온 파인드

+10

무방향 그래프에는 n개의 노드가 있으며, 노드 번호는 0부터 n-1까지입니다. edges의 각 항목 [u, v]는 노드 u와 v를 연결하며, 간선은 어느 방향으로든 이동할 수 있습니다. 간선을 따라 source에서 destination까지 이동할 수 있으면 true를 반환하고, 그렇지 않으면 false를 반환하세요. 노드는 항상 자기 자신에게 도달할 수 있습니다.

함수

validPath(n: integer, edges: integer-2d-array, source: integer, destination: integer) → boolean

ninteger: 노드의 수
edgesinteger-2d-array: 각각 연결된 노드 쌍 [u, v]인 간선
sourceinteger: 시작하는 노드
destinationinteger: 도달하려는 노드
반환값boolean: 어떤 경로가 소스와 대상을 연결하는지 여부

제약 조건

2 ≤ n ≤ 10⁴
1 ≤ edges.length ≤ 5000
edges[i] = [u, v]이며 0 ≤ u, v ≤ n-1이고 u ≠ v
어느 방향으로든 간선이 두 번 나타나지 않습니다.
0 ≤ source, destination ≤ n-1

예제

입력: n = 6edges = [[0, 1], [1, 2], [2, 3], [4, 5]]source = 0destination = 3
출력: true
설명: 0 → 1 → 2 → 3 경로는 간선 세 개를 사용하므로 노드 3에 도달할 수 있습니다. 노드 4와 5는 경로에서 필요하지 않은 별도의 부분을 이룹니다.

입력: n = 5edges = [[0, 1], [0, 2], [3, 4]]source = 2destination = 4
출력: false
설명: 노드 2에서 0에 도달한 다음 1에 도달하며, 그 외에는 아무것도 도달하지 못합니다. 노드 4는 노드 3에만 연결되어 있고, {0, 1, 2}와 {3, 4}를 연결하는 간선이 없으므로 답은 false입니다.

제출 시 숨은 테스트 +16개

후속 질문

간선이 단방향이라고 가정해 봅시다. [u, v]는 u에서 v로만 이동할 수 있게 합니다. 세 가지 접근 방식 중 어떤 것이 여전히 작동하며, 각각에서 무엇을 변경해야 할까요?

힌트

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

3개 중 0개 열림

풀이

질문은 source와 destination이 그래프의 같은 연결 요소에 속하는지입니다. 느린 방법은 더 이상 새로 도달하는 노드가 없을 때까지 간선 목록을 다시 훑습니다. 인접 리스트를 이용한 너비 우선 탐색은 각 노드와 간선을 한 번씩 탐색하며, 서로소 집합 자료 구조는 간선을 읽으면서 그룹을 합쳐 같은 답을 얻습니다. 이 방법에는 이웃 목록이 전혀 필요하지 않습니다.

더 이상 변화가 없을 때까지 가장자리를 훑습니다

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

핵심 아이디어

도달할 수 있다는 것을 아는 모든 노드에 표시를 하세요. source부터 시작합니다. 이제 간선 목록을 읽으세요. 한쪽 끝은 표시되어 있고 다른 쪽 끝은 표시되어 있지 않은 간선이 있다면, 표시되지 않은 쪽 끝에도 도달할 수 있으므로 표시하세요. 한 번 훑는 동안 새로운 표시가 없거나 destination에 표시가 될 때까지 전체 과정을 반복하세요.

이 방법이 올바른 이유는 다음과 같습니다. source에서 길이가 k인 경로에 있는 노드는 늦어도 k번째 순회에서 표시되며, 표시된 노드에서 간선이 이어지는 경우에만 노드에 표시가 됩니다. 첫 번째 예에서는 목록 순서대로 한 번 훑으면 차례로 1, 2, 3에 표시가 되므로 작업이 끝납니다.

비용은 간선의 순서에 따라 달라집니다. 경로가 먼 쪽 끝에서부터 거꾸로 나열되어 있다면, 한 번 훑을 때마다 노드가 하나씩만 더 표시됩니다. 그러면 노드 5001개를 지나는 경로는 간선 5000개를 5000번 훑어야 하므로, 간선 확인 횟수는 2.5 × 10^7회입니다. 이웃 목록을 한 번 훑으면 되는 경우와 비교해 보세요.

알고리즘

source만 표시된 reached를 만드세요.
모든 간선 [u, v]을 확인하세요. 한쪽 끝만 표시되어 있으면 다른 쪽 끝도 표시하고 변경 사항이 있었음을 기록하세요.
변경 사항이 있고 destination이 아직 표시되지 않은 동안 확인을 반복하세요.
destination이 표시되었는지 반환하세요.

def validPath(n, edges, source, destination):
    reached = [False] * n
    reached[source] = True
    changed = True
    while changed and not reached[destination]:
        changed = False
        for u, v in edges:
            # An edge with exactly one reached end pulls the other end in.
            if reached[u] != reached[v]:
                reached[u] = reached[v] = True
                changed = True
    return reached[destination]

너비 우선 탐색

핵심 아이디어

스윕은 양 끝점이 이미 오래전에 확정된 간선을 다시 읽느라 시간을 낭비합니다. 대신 각 노드에 대해 그 노드와 연결된 노드들을 나열하세요. 각 간선 [u, v]은 양쪽 목록에 들어갑니다. 양방향으로 이동할 수 있기 때문입니다. 그런 다음 source에서 바깥쪽으로 탐색하세요. 큐에서 노드를 하나 꺼내고, 아직 방문하지 않은 각 이웃을 큐에 넣습니다.

노드를 큐에서 꺼낼 때가 아니라 큐에 넣을 때 방문한 것으로 표시하세요. 그러면 어떤 노드도 큐에 두 번 들어가지 않으며, 0 → 1 → 2 → 0처럼 그래프에 사이클이 있어도 탐색이 끝납니다. destination이 큐에서 꺼내지는 경우 경로가 존재합니다. 큐가 먼저 비면 source에서 도달할 수 있는 모든 노드를 방문한 것이며, 그중에 destination은 없었던 것입니다.

각 노드는 최대 한 번 큐에 들어가고 각 간선은 양 끝에서 한 번씩, 총 두 번 확인하므로 간선이 m개일 때 시간 복잡도는 O(n + m)입니다. 이웃 목록에는 O(n + m)의 공간이 필요합니다. 재귀 대신 큐를 사용하면 5000개 노드로 이루어진 경로를 탐색할 때 호출 스택이 넘치는 것을 방지할 수 있습니다.

알고리즘

인접 리스트를 구성합니다. 각 간선 [u, v]에 대해 v를 u의 리스트에 추가하고 u를 v의 리스트에 추가합니다.
source를 방문한 것으로 표시하고 큐에 넣습니다.
맨 앞에서 노드를 꺼냅니다. 노드가 destination이면 true를 반환합니다.
아직 방문하지 않은 각 이웃을 방문한 것으로 표시하고 큐에 넣습니다.
큐가 비면 false를 반환합니다.

from collections import deque


def validPath(n, edges, source, destination):
    # Each edge goes both ways, so list it under both of its ends.
    graph = [[] for _ in range(n)]
    for u, v in edges:
        graph[u].append(v)
        graph[v].append(u)
    seen = [False] * n
    seen[source] = True
    queue = deque([source])
    while queue:
        node = queue.popleft()
        if node == destination:
            return True
        for nxt in graph[node]:
            if not seen[nxt]:
                # Mark on push, so no node enters the queue twice.
                seen[nxt] = True
                queue.append(nxt)
    return False

유니온-파인드

핵심 아이디어

경로 자체는 필요 없고, 경로가 존재하는지만 알면 됩니다. 따라서 그래프를 서로 연결된 노드들의 그룹으로 취급하세요. 처음에는 각 노드가 각각 하나의 그룹입니다. 간선 [u, v]는 u와 v가 같은 그룹에 속한다는 뜻이므로, 두 그룹을 합칩니다. 모든 간선을 처리한 후에는 source와 destination이 같은 그룹에 속할 때만 서로 연결되어 있습니다.

각 그룹은 parent 링크가 있는 트리로 저장하고, 루트가 그룹을 나타냅니다. find(x)는 루트까지 위로 올라갑니다. 그룹을 합치려면 한쪽 루트를 다른 쪽 루트 아래에 둡니다. 두 번째 예시에서 [0, 1]과 [0, 2]는 그룹 {0, 1, 2}를 만들고, [3, 4]는 {3, 4}를 만듭니다. find(2)와 find(4)는 서로 다른 루트를 반환하므로 답은 false입니다.

두 가지 방법으로 트리를 평평하게 유지할 수 있습니다. 작은 그룹을 큰 그룹 아래에 두고, find를 수행하는 동안 각 노드가 조부모를 가리키도록 해 경로를 절반으로 줄입니다. 이 두 방법을 함께 사용하면 각 연산의 비용은 α(n), 즉 역 아커만 함수가 됩니다. 이 값은 여러분이 접할 수 있는 어떤 입력에서도 5보다 작습니다. 간선은 한 번만 읽고 parent와 size만 저장하므로 공간은 O(n)이며, 인접 노드 목록을 만들 필요도 없습니다.

알고리즘

모든 노드에 대해 parent[x] = x와 size[x] = 1을 설정합니다.
각 간선 [u, v]에 대해 양 끝의 루트 a와 b를 찾습니다.
두 루트가 다르면 더 작은 그룹의 루트를 다른 그룹의 루트 아래에 두고 크기를 더합니다.
find(source)와 find(destination)이 같은지 반환합니다.

def validPath(n, edges, source, destination):
    parent = list(range(n))  # every node starts as its own group
    size = [1] * n

    def find(x):
        # Walk up to the group's 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)
        if a != b:
            # 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 find(source) == find(destination)

함정과 경계 사례

그래프는 작지만, 탐색이 끝나고 올바른 답을 얻을 수 있는지는 몇 가지 세부 사항에 달려 있습니다.

각 간선을 한 방향으로만 추가하는 경우. 그래프는 무방향이므로 [1, 0]이 있으면 0에서 1로도 이동할 수 있어야 합니다. 한쪽 방향으로만 연결된 인접 리스트에서는 간선을 거꾸로 이용하는 경로를 찾지 못합니다.
노드를 큐에 넣을 때가 아니라 큐에서 꺼낼 때 방문한 것으로 표시하는 경우. 그러면 해당 노드보다 먼저 처리되는 각 이웃마다 노드가 큐에 한 번씩 들어가므로, 큐에는 최대 n개가 아니라 2m개까지 들어갈 수 있습니다.
source와 destination이 같을 수 있다는 점을 잊는 경우. 해당 노드에 간선이 전혀 없어도 답은 true입니다.
긴 경로에서 재귀 DFS를 사용하는 경우. 5000개 노드를 지나는 경로는 5000단계의 중첩 호출을 발생시켜 Python의 기본 제한인 1000을 넘습니다. 큐나 명시적 스택을 사용하세요.
유니온-파인드에서 parent[source]와 parent[destination]을 비교하는 경우. 루트만이 그룹을 나타냅니다. 항상 find(source)와 find(destination)을 비교하세요.
배열이 1부터 시작하는 Lua와 R에서 인덱스 이동을 잊는 경우: 노드 x는 인덱스 x+1에 있습니다.

자주 묻는 질문4

경로가 존재하는지 확인하려면 BFS, DFS, 유니온 파인드 중 무엇을 사용해야 하나요?

세 가지 모두 선형이거나 선형에 가깝습니다. BFS와 DFS는 목적지에 도달하는 즉시 멈출 수 있으며 경로 자체를 반환할 수도 있습니다. Union-find는 인접 리스트가 필요 없고 각 간선을 한 번씩 읽습니다. 같은 그래프에 대해 연결성 질문이 많을 때 특히 유용한데, 병합 후에는 질문마다 find 호출 두 번이면 되기 때문입니다.

그래프에 경로가 존재하는지 확인하는 시간 복잡도는 얼마인가요?

BFS 또는 DFS를 사용하면 노드가 n개이고 간선이 m개일 때 시간과 공간 복잡도는 O(n + m)입니다. 각 노드는 한 번 방문하고 각 간선은 양쪽 끝에서 확인합니다. 크기 기준 union과 경로 절반 줄이기를 사용하는 유니온-파인드는 시간 복잡도가 O(n + m·α(n))이고 공간 복잡도는 O(n)입니다. 여기서 α는 증가 속도가 매우 느려 실제로는 작은 상수로 볼 수 있습니다.

BFS에 방문 배열이 필요한 이유는 무엇인가요?

이것이 없으면 0 → 1 → 2 → 0과 같은 순환으로 인해 검색이 끝없이 반복되고, 순환이 없더라도 여러 이웃이 있는 노드는 이웃마다 한 번씩 대기열에 추가됩니다. 각 노드를 대기열에 추가하는 순간 표시하면 각 노드가 한 번만 처리되므로 작업량이 O(n + m)으로 제한됩니다.

유니온 파인드에서 경로 압축과 크기 기반 합치기는 어떤 역할을 하나요?

find가 빠르게 유지되도록 트리의 깊이를 얕게 유지합니다. 크기 기준 합치기는 더 작은 트리를 더 큰 트리 아래에 연결하므로, 노드의 깊이는 해당 노드가 속한 그룹의 크기가 최소 두 배가 될 때만 증가하며, 따라서 깊이는 log n으로 제한됩니다. 경로 압축 또는 여기서 사용된 경로 절반 나누기는 루트까지의 경로를 따라갈 때마다 그 경로를 짧게 만듭니다. 이 두 가지를 함께 사용하면 각 연산의 시간 복잡도를 α(n)으로 낮춥니다.

Python

def validPath(n, edges, source, destination):
    # 여기에 코드를 작성하세요

테스트 케이스

케이스 1

케이스 2

입력

n = 6
edges = [[0, 1], [1, 2], [2, 3], [4, 5]]
source = 0
destination = 3

기대값

true

Find if Path Exists in Graph

함수

제약 조건

예제

힌트

풀이

더 이상 변화가 없을 때까지 가장자리를 훑습니다

너비 우선 탐색

유니온-파인드

함정과 경계 사례

자주 묻는 질문4

비슷한 문제