Kruskal 검색 결과
3 개의 검색 결과가 있습니다.
개발/알고리즘

[백준 1922] 네트워크 연결 (python)

1922번: 네트워크 연결 이 경우에 1-3, 2-3, 3-4, 4-5, 4-6을 연결하면 주어진 output이 나오게 된다. www.acmicpc.net 모든 컴퓨터를 연결해야하므로 Kruskal 알고리즘을 사용하자 arr에 간선들을 저장한뒤 비용을 기준으로 정렬을 한다. 두 컴퓨터의 root를 찾은뒤 같지 않다면 비용을 더해주고 더 큰 root값의 root를 작은 root로 바꾸어준다. import sys input = sys.stdin.readline N = int(input()) M = int(input()) arr = [] root = [i for i in range(N+1)] for _ in range(M): s, e, v = map(int, input().split()) arr.append(..

2021. 5. 4. 17:26
개발/알고리즘

[백준 1717] 집합의 표현 (python)

1717번: 집합의 표현 첫째 줄에 n(1 ≤ n ≤ 1,000,000), m(1 ≤ m ≤ 100,000)이 주어진다. m은 입력으로 주어지는 연산의 개수이다. 다음 m개의 줄에는 각각의 연산이 주어진다. 합집합은 0 a b의 형태로 입력이 주어진다. 이는 www.acmicpc.net Kruskal 알고리즘을 이용하자 모든 수가 처음에 자기 자신을 root로 가지는 root배열을 생성한다. findRoot함수를 통해 입력받은 두 수의 root를 찾는다. q가 0이면 두 root를 비교하여 출력한다. q가 1이면 더 큰 root의 root를 작은 root로 바꾸어준다. import sys sys.setrecursionlimit(10**6) input = sys.stdin.readline N, M = ma..

2021. 5. 3. 17:30
개발/알고리즘

[백준 1197] 최소 스패닝 트리 (python)

1197번: 최소 스패닝 트리 첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 www.acmicpc.net 최소 신장 트리(minimum spanning tree​) 전체 요소들을 연결할 때 사용한다. Kruskal 알고리즘, Prim 알고리즘이 있다. Kruskal 간선들을 정렬 간선이 잇는 두 정점의 root를 찾는다. 다르다면 하나의 root를 바꾸어 연결 시켜준다. Prim 임의의 정점을 선택 해당 정점에서 갈 수 있는 간선을 minheap에 넣는다. 최소값을 뽑아 해당 정점을 방문 안했다면 선택한다. Kruska..

2021. 4. 18. 02:48