하루살이 개발자

최소스패닝트리 문제입니다. 문제링크:https://www.acmicpc.net/problem/1197 1197번: 최소 스패닝 트리 첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 www.acmicpc.net 풀이 크루스칼 알고리즘, Union+find 알고리즘 이용하는 문제 Code # 최소 스패닝 트리 # 크루스칼 알고리즘 import sys input = sys.stdin.readline v, e = map(int, input().split()) # 부모 테이블 초기화 parent = [0] * (v+1) for i..

1. 신장 트리 - 그래프에서 모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프를 의미한다. * 모든 노드가 포함되어 서로 연결되면서 사이클이 존재하지 않는 다는 조건은 트리의 조건이기도 한다. 2. 최소 신장 트리 - 최소한의 비용으로 구성되는 신장 트리를 찾아야 할 때 - 크루스칼/프림 알고리즘 1) 크루스칼 알고리즘 - 대표적인 최소 신장 트리 알고리즘이다. - 그리디 알고리즘으로 분류된다. [동작 과정] 1. 간선 데이터를 비용에 따라 오름차순으로 정렬한다.(비용이 적은 순으로 나열) 2. 간선을 하나씩 확인하며 현재의 간선이 사이클을 발생시키는지 확인한다. 1) 사이클이 발생하지 않는 경우 최소 신장 트리에 포함시킨다. 2) 사이클이 발생하는 경우 최소 신장 트리에 포함시키지 않는다. ..