Graph Valid Tree
n개의 노드가 주어집니다. 노드는 0부터 n-1까지 번호가 매겨져 있으며, 무방향 간선 목록 edges도 주어집니다. 각 쌍 [a, b]는 노드 a와 노드 b를 연결합니다.
간선들이 모든 n개의 노드를 하나의 트리로 만들면 true를 반환합니다. 즉, 모든 노드는 다른 모든 노드에 도달할 수 있고 사이클이 없어야 합니다. 그렇지 않으면 false를 반환합니다.
함수
- ninteger
- 0부터 n-1까지 번호가 매겨진 노드의 개수
- edgesinteger-2d-array
- 무방향 간선으로, 각각 [a, b] 쌍입니다
- 반환값boolean
- 간선들이 모든 n개의 노드를 하나의 트리로 연결하면 true, 그렇지 않으면 false
제약 조건
2 ≤ n ≤ 1041 ≤ edges.length ≤ 5000edges[i] = [a, b]이며0 ≤ a, b ≤ n-1이고a ≠ b- 어느 방향에서든 동일한 간선이 두 번 나타나지 않습니다.
예제
- 입력
- n = 5edges = [[0, 1], [0, 2], [0, 3], [1, 4]]
- 출력
- true
- 설명
- 노드 0은 노드 1, 2, 3에 연결되어 있고, 노드 4는 노드 1에 매달려 있습니다. 네 개의 간선이 고리 없이 다섯 개의 노드를 모두 연결하므로 이것은 트리입니다.
- 입력
- n = 5edges = [[0, 1], [1, 2], [2, 3], [1, 3], [1, 4]]
- 출력
- false
- 설명
[1, 2],[2, 3],[1, 3]간선은 1, 2, 3, 1의 순환을 이룹니다. 다섯 개의 노드에 있는 다섯 개의 간선은 트리가 가질 수 있는 것보다 하나 더 많습니다.
- 입력
- n = 4edges = [[0, 1], [1, 2], [2, 0]]
- 출력
- false
- 설명
- 간선은 3개로,
n-1이지만 0, 1, 2, 0으로 루프를 이루며 노드 3에는 간선이 전혀 없습니다.
후속 질문
그래프가 트리가 아닌 경우, 트리로 만들려면 간선을 몇 개 제거하고 몇 개 추가해야 할까요? 한 번의 순회로 둘 다 셀 수 있을까요?
힌트
하나씩 열어 보세요. 열 때마다 조금 더 알려 줍니다.
트리가 아닌 작은 그래프를 몇 개 그려 보세요. 실패하는 방법은 두 가지뿐입니다. 무엇일까요?
그래프는 사이클이 있거나 일부 노드가 고립되어 있으면 트리가 아닙니다.
n개의 노드로 이루어진 트리는 정확히n-1개의 간선을 가지며, 간선이 정확히n-1개라면 이 두 가지 문제는 항상 함께 발생합니다. 따라서 개수를 확인한 다음 두 가지 중 하나를 확인하세요.모든 노드가 처음에는 각각 따로 있다고 하자. 각 간선에 대해 양 끝이 이미 같은 그룹에 속해 있는지 확인한다. 그렇다면 그 간선은 사이클을 닫고, 그렇지 않다면 두 그룹을 합친다. 유니온 파인드 자료 구조는 거의 상수 시간에 이 질문에 답한다.
풀이
트리는 연결되어 있고 사이클이 없습니다. 간선이 정확히 n-1개라면 이 두 조건은 하나의 조건입니다. 즉, 이러한 그래프는 사이클이 없을 때에만 연결되어 있습니다. 따라서 먼저 간선 수를 확인한 다음, 연결성을 한 번 탐색하거나 유니온 파인드로 이미 연결된 두 노드를 잇는 간선을 찾아내면 됩니다.
모든 간선 앞에서 경로를 검색합니다
정답이지만 가장 큰 테스트에서는 끝나지 않음
핵심 아이디어
간선을 하나씩 추가합니다. [u, v]를 추가하기 전에 지금까지 추가된 간선을 따라 u에서 탐색합니다. v에 도달할 수 있다면 새 간선은 두 노드 사이의 두 번째 경로가 되어 사이클을 형성합니다. 두 번째 예에서 [1, 3]이 그러한 경우입니다. 어떤 간선도 사이클을 형성하지 않으면 그래프는 포리스트이며, 마지막으로 노드 0에서 탐색하면 그래프가 하나의 트리인지 알 수 있습니다.
각 검사에서는 지금까지 구성된 그래프 전체를 탐색합니다. 간선이 순서대로 추가되는 5001개 노드의 경로에서는 탐색으로 1 + 2 + ... + 5000개의 노드를 방문하며, 이는 약 1250만 개입니다.
알고리즘
- 각 노드에 대해 비어 있는 인접 리스트로 시작합니다.
- 각 간선
[u, v]에 대해 지금까지 추가된 간선을 따라u에서 탐색합니다.v에 도달하면false를 반환합니다. - 그렇지 않으면 양쪽 끝 노드의 리스트에 간선을 추가합니다.
- 마지막으로, 노드 0에서 시작한 탐색이
n개의 모든 노드에 도달하는지 반환합니다.
def reachable(graph, start):
# Every node a search from start can reach, using the edges added so far.
seen = [False] * len(graph)
seen[start] = True
stack = [start]
while stack:
node = stack.pop()
for nxt in graph[node]:
if not seen[nxt]:
seen[nxt] = True
stack.append(nxt)
return seen
def validTree(n, edges):
graph = [[] for _ in range(n)]
for u, v in edges:
# A path from u to v already exists, so this edge closes a cycle.
if reachable(graph, u)[v]:
return False
graph[u].append(v)
graph[v].append(u)
# No cycle anywhere. A tree also needs every node reachable from node 0.
return all(reachable(graph, 0))간선을 세고, 한 번 검색하세요
핵심 아이디어
n개의 서로 분리된 노드에서 시작해 간선을 하나씩 추가하세요. 각 간선은 두 그룹을 연결해 그룹 수를 하나 줄이거나, 한 그룹 안에 놓여 사이클을 만듭니다. 그룹 하나에 도달하려면 n-1번 연결해야 합니다. 따라서 n-1개보다 적은 간선으로는 그래프를 연결할 수 없고, 그보다 많으면 사이클이 생깁니다. 두 번째 예시에서는 노드 5개에 간선 5개가 있어 개수만으로도 조건을 만족하지 못합니다.
간선이 정확히 n-1개일 때, 모든 간선이 연결을 만들었을 경우, 즉 사이클을 만든 간선이 하나도 없을 경우에만 그래프가 하나의 그룹으로 끝납니다. 따라서 개수가 맞으면 연결성만 확인하세요. 노드 0에서 한 번 탐색해 n개 노드 모두에 도달해야 합니다. 세 번째 예시에서는 0, 1, 2에만 도달합니다. m = n-1일 때, 리스트와 탐색의 시간 복잡도는 O(n)입니다.
알고리즘
edges.length가n-1이 아니면false를 반환합니다.- 인접 리스트를 만들고, 각 간선을 양쪽 끝 노드에 모두 저장합니다.
- 노드 0을 스택에 넣고 방문한 것으로 표시합니다.
- 노드를 꺼내고, 아직 방문하지 않은 모든 이웃 노드를 방문한 것으로 표시하고 개수를 세면서 스택에 넣습니다.
- 개수가
n과 같은지 반환합니다.
def validTree(n, edges):
# A tree on n nodes has exactly n-1 edges.
if len(edges) != n - 1:
return False
graph = [[] for _ in range(n)]
for u, v in edges:
graph[u].append(v)
graph[v].append(u)
# With n-1 edges, the graph is a tree exactly when it is connected.
seen = [False] * n
seen[0] = True
stack = [0]
reached = 1
while stack:
node = stack.pop()
for nxt in graph[node]:
if not seen[nxt]:
seen[nxt] = True
reached += 1
stack.append(nxt)
return reached == n간선 세기와 유니온 파인드
핵심 아이디어
Union-find는 탐색 없이 각 간선에 대해 사이클 여부를 판별합니다. 모든 노드는 처음에 자기 자신의 그룹으로 시작합니다. 간선 [u, v]에 대해 양쪽 끝점의 루트를 찾습니다. 루트가 다르면 간선이 두 부분을 연결하므로 두 그룹을 합칩니다. 루트가 같으면 u와 v는 이미 연결되어 있고, 해당 간선이 사이클을 만듭니다. 모든 간선이 그룹을 합치는 n-1개의 간선이 있으면, n개의 그룹은 하나로 합쳐집니다. 즉, 트리가 됩니다.
두 가지 규칙으로 부모 체인을 짧게 유지합니다. 그룹을 합칠 때 작은 그룹의 루트를 큰 그룹의 루트 아래에 연결하므로, 노드가 10^4개일 때 체인의 길이는 13단계를 넘지 않습니다. find를 수행하는 동안 지나치는 각 노드가 자신의 조부모를 가리키도록 합니다. 이 두 규칙을 함께 적용하면 m번의 연산에 드는 비용은 O(m α(n))이며, 여기서 α는 역 아커만 함수로, 이 경우 최대 4입니다. 공간 복잡도는 O(n)입니다.
알고리즘
edges.length가n-1이 아니면false를 반환합니다.- 모든 노드에 대해
parent[x] = x로 설정하고 그룹 크기를 1로 설정합니다. - 각 간선
[u, v]에 대해u와v에서 시작해 루트까지 부모를 따라가며, 지나가는 각 노드가 조부모를 가리키도록 합니다. - 루트가 같으면
false를 반환합니다. - 루트가 다르면 더 작은 그룹의 루트를 다른 그룹에 연결하고 그 크기를 더합니다.
- 모든 간선이 두 그룹을 병합했다면
true를 반환합니다.
def validTree(n, edges):
# A tree on n nodes has exactly n-1 edges.
if len(edges) != n - 1:
return False
parent = list(range(n)) # every node starts as its own group
size = [1] * n
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)
# The two ends are already joined: this edge closes a cycle.
if a == b:
return False
# Hang the smaller group under the larger one.
if size[a] < size[b]:
a, b = b, a
parent[b] = a
size[a] += size[b]
# n-1 merges with no cycle turn the n groups into one.
return True
함정과 경계 사례
- 사이클만 확인하기. 노드 6개에 간선이 3개인 경우 사이클은 없지만, 세 부분으로 나뉩니다.
- 간선 수만 확인하기. 세 번째 예시에는
n-1개의 간선이 있지만, 루프 0, 1, 2가 노드 3에 필요한 간선을 사용합니다. - 각 간선을 한쪽 끝에만 저장하기.
[1, 0]도 노드 0과 1을 연결하므로, 노드 0에서 시작한 탐색은 노드 1을 놓칩니다. - 부모 노드를 건너뛰지 않는 깊이 우선 사이클 검사. 모든 간선은 방금 떠나온 노드로 곧장 되돌아가므로, "방문한 이웃을 만남" 조건이 모든 트리에서 실행됩니다.
- 긴 경로를 재귀적으로 탐색하기. 노드 5001개로 이루어진 선형 구조는 호출 깊이가 5000까지 내려가 Python의 기본 제한인 1000을 넘으므로, 명시적인 스택을 사용하세요.
자주 묻는 질문3
Graph Valid Tree의 시간 복잡도는 무엇인가요?
깊이 우선 탐색을 사용하면 O(n + m)이며, 여기서 m은 간선의 수입니다. 유니온-파인드를 사용하면 O(n + m α(n))입니다. 두 방법 모두 먼저 간선 수를 확인하므로, 수가 잘못된 그래프는 탐색을 시작하기 전에 거부됩니다.
노드가 n개인 트리에는 왜 간선이 n-1개 있을까요?
하나의 노드에서 트리를 시작해 나머지 노드를 한 번에 하나씩 추가하세요. 새 노드는 정확히 하나의 간선과 함께 추가됩니다. 간선이 없으면 연결이 끊기고, 두 개 있으면 사이클이 생깁니다. 따라서 n개의 노드에는 n-1개의 간선이 필요합니다.
무방향 그래프에서 사이클을 어떻게 감지하나요?
유니온-파인드에서는 양 끝점이 이미 같은 루트를 공유하는 간선이 사이클을 형성합니다. 깊이 우선 탐색에서는 사이클이란 도착해 온 노드가 아닌 방문한 이웃을 뜻하므로, 각 노드의 부모를 추적합니다. 유니온-파인드에는 부모도 인접 리스트도 필요하지 않습니다.
비슷한 문제
같은 아이디어를 쓰는 문제입니다. 두세 개를 풀면 패턴이 몸에 익습니다.
def validTree(n, edges):
# 여기에 코드를 작성하세요테스트 #1
테스트 #2
테스트 #3
인자들
n = 5 edges = [[0, 1], [0, 2], [0, 3], [1, 4]]
예상 출력
true