728x90
반응형
문제 바로가기
문제:
그래프가 주어졌을 때, 그 그래프의 최소 스패닝 트리를 구하는 프로그램을 작성하시오. 최소 스패닝 트리는, 주어진 그래프의 모든 정점들을 연결하는 부분 그래프 중에서 그 가중치의 합이 최소인 트리를 말한다.
입력:
첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 가중치 C인 간선으로 연결되어 있다는 의미이다. C는 음수일 수도 있으며, 절댓값이 1,000,000을 넘지 않는다. 그래프의 정점은 1번부터 V번까지 번호가 매겨져 있고, 임의의 두 정점 사이에 경로가 있다. 최소 스패닝 트리의 가중치가 -2,147,483,648보다 크거나 같고, 2,147,483,647보다 작거나 같은 데이터만 입력으로 주어진다.
출력:
첫째 줄에 최소 스패닝 트리의 가중치를 출력한다.
풀이과정 :
import sys
sys.stdin = open('/Users/song/Desktop/Python/Python/h.txt', 'r')
N ,M = map(int,sys.stdin.readline().split(" "))
graph = []
# 간선체크
for i in range(M):
a, b, c = map(int,sys.stdin.readline().rstrip().split(" "))
graph.append((a,b,c))
# 자기자신이 부모
parent = [i for i in range(N+1)]
graph.sort(key=lambda x:x[2])
def find(x):
# 자기 자신이 부모가 아니면
if x != parent[x] :
parent[x] = find(parent[x])
return parent[x]
res = 0
for x, y, c in graph:
X = find(x)
Y = find(y)
# 사이클을 형성하지 않은경우
if X != Y :
# X 가 Y 보다 크면
if X > Y :
# 작은 수 가 부모임
parent[X] = y
else:
parent[Y] = X
res += c
print(res)
이유 graph 정렬을 안해줘서 틀림
크루스칼 알고리즘은 간선을 중심으로 한다.
하지만 프림 알고리즘은 정점 중심으로 한다.
bfs인데 heap을 사용하는것 같다.
2. Prim
N,M = map(int,sys.stdin.readline().split(" "))
visited = [False]*(N+1)
lst = [[] for _ in range(N+1)]
heap = [[0, 1]]
for _ in range(M):
# 간선 , 가중치
s, e, w = map(int, input().split())
lst[s].append([w, e])
lst[e].append([w, s])
count = 0
res = 0
while heap:
if count == N:
break
a, b = heapq.heappop(heap)
if not visited[b]:
visited[b] = True
res += a
count += 1
for i in lst[b]:
heapq.heappush(heap,i)
print(res)
위에는 프림, 아래는 크루스칼이다.
- 프림 알고리즘의 시간 복잡도: O(E log V) 또는 O(V^2)
- E: 간선의 개수
- V: 정점의 개수
- 크루스칼 알고리즘의 시간 복잡도: O(E log E) 또는 O(E log V)
- E: 간선의 개수
- V: 정점의 개수
- 프림 알고리즘:
- 간선의 개수(E)가 정점의 개수(V)보다 작은 경우 (E << V^2)
- 간선들이 힙(Heap) 자료구조로 구현되기 때문에 간선의 개수가 상대적으로 작을 때 효율적입니다.
- 특히, 밀집 그래프(Dense Graph)에서 크루스칼보다 효율적입니다.
- 크루스칼 알고리즘:
- 간선의 개수(E)가 매우 큰 경우 (E가 V^2에 가까운 경우)
- 크루스칼 알고리즘은 간선들을 정렬하는 과정에서 O(E log E)의 시간이 들기 때문에 간선의 개수가 많은 경우에 유리합니다.
- 희소 그래프(Sparse Graph)에서 프림보다 효율적입니다.
반응형
댓글