가중된 무방향 그래프가 주어진다고 가정합니다. 두 개의 꼭짓점과 비용 '제한'을 입력으로 사용하고 입력으로 주어진 비용보다 더 낮은 비용 경로가 있는지 확인하는 함수 쿼리를 구현해야 합니다. 경로가 있으면 true를 반환하고 그렇지 않으면 false를 반환합니다.
따라서 입력이 다음과 같으면
쿼리는 (0, 2, 10), (3, 1, 30), (4, 3, 30)입니다.
그러면 출력은
FalseTrueTrue
비용 10의 정점 0에서 2 사이에 경로가 없기 때문에 첫 번째 쿼리의 결과는 False입니다.
두 번째 쿼리의 결과는 비용 10의 꼭짓점 3에서 1 사이의 경로가 30보다 작기 때문에 True입니다.
세 번째 쿼리의 결과는 비용 30의 꼭짓점 4에서 3 사이의 경로가 30이므로 True입니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
-
weights :=그래프의 다른 가중치를 포함하는 목록
-
연결 :=가중치에 대한 연결을 포함하는 목록
-
query() 함수를 정의합니다. 이것은 p, q, limit이 필요합니다.
-
index :=정렬된 순서를 유지하기 위해 왼쪽에 추가할 수 있습니다.
-
인덱스가 0과 같으면
-
거짓을 반환
-
-
연결[인덱스-1, p]가 연결[인덱스-1, q]
과 같으면 True를 반환합니다.
-
예시
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
import bisectclass Solution(object):def __init__(self, n, edgeList):def find(node):if parent[node]!=node:parent[node] =find(parent[node]) return parent[ 노드] def union(x,y):parent[find(y)] =find(x) return parent ={i:i for i in range(n)} edgeList.sort(key =람다 x:x[2] ) self.connections =[] self.weights =[] for index,(i,j,weight) in enumerate(edgeList):union(i,j) if index!=len(edgeList)-1 and weight ==edgeList [index+1][2]:계속 self.weights.append(weight) self.connections.append([find(i) for i in parent]) def query(self, p, q, limit):index =bisect .bisect_left(self.weights,limit) if index==0:False return self.connections[index-1][p] ==self.connections[index-1][q]ob =Solution(5, [[ 0, 1, 10], [0, 2, 20], [1, 4, 10], [0, 3, 10], [1, 2, 20], [2, 3, 10]])print( ob.query(0, 2, 10))print(ob.query(3, 1, 30))print(ob.query(3, 1, 30)) 쿼리(4, 3, 30)) 입력
ob =솔루션(5, [[0, 1, 10], [0, 2, 20], [1, 4, 10], [0, 3, 10], [1, 2, 20], [2, 3, 10]])print(ob.query(0, 2, 10))print(ob.query(3, 1, 30))print(ob.query(4, 3, 30))출력
FalseTrueTrue