크루스칼

[그래프, 최소 스패닝 트리(크루스칼, 프림)] BOJ 4386 별자리 만들기

문제 문제 접근 방식 n 개의 별을 이어서 별자리를 만듬 -> 그래프 문제 모든 별이 직 간접적으로 이어져 있어야 함 -> 스패닝 트리 최소 비용 -> 최소 스패닝 트리 -> 크루스칼 또는 프림으로 해결 가능 답 1. 크루스칼 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 import sys import math input = sys.stdin.readline n = int(input()) stars = [list(map(float, input().split())) for _ in range(n)] graph = [] parent = [i for i in range(n)..

[Graph] BOJ 1197 최소 스패닝 트리

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 import sys input = sys.stdin.readline V, E = map(int, input().split()) inputs = [list(map(int, input().split())) for _ in range(E)] parents = [i for i in range(0, V+1)] graph = [] for i in inputs: A, B, C = i graph.append((C, A, B)) graph.sort() def find(parents, x): if parents[x] != x: parents[x] ..

그래프 관련 알고리즘 요약 정리 (크루스칼, 프림, 위상 정렬)

그래프를 사용하는 알고리즘은 뭐가 있을까? - 크루스칼, 프림, 위상 정렬 https://seclab-j.tistory.com/86 그래프 이론 요약 정리 그래프란? 그래프란 정점(Edge)과 간선(Vertex/Node)으로 이루어진 자료구조를 의미한다. 그림으로 나타내자면 다음과 같다. 차수(degree)는 간선으로 연결된 이웃한 정점의 개수를 의미한다. 그래프는 seclab-j.tistory.com 앞선 정리 내용에서는 코드로 그래프를 어떻게 표현하는가를 중점적으로 살펴보았다. (인접 행렬과 인접 리스트..) 오늘은 여기서 좀 더 나아가 그래프를 사용하는 알고리즘에는 무엇이 있으며 어떻게 사용하는지에 대해서 다루어 보고자 한다. 먼저 복잡도를 언급해보자면 다음과 같다. 알고리즘 종류 시간 복잡도 크루..