백준 1197

<최소신장트리 구하기>

난이도 : 골드 4

1. 백준 문제
   1197

2. 코드 알고리즘

• 최소신장트리

• 1197

2-1. 슈도 코드

1197 슈도코드

n, m 
에지 정보를 저장할 우선순위 큐 (항상 가중치가 정렬되야 하므로)
대표노드 저장 리스트

for M:
	우선순위 큐에 에지 정보 저장(가중치 우선으로 정렬되도록 하기)

#유니온 파인드 연산 
#find 연산 
find(a):
	a가 대표노드면 리턴
	a의 대표 노드값을 find(parent[a])로 설정
#union 연산
union(a, b):
	a와 b의 대표노드 찾기
	두 원소의 대표 노드끼리 연결

#최소신장트리

while 에지수가 N-1 될때까지:
	큐에서 에지 정보 가져오기
	if 에지 시작점과 끝점의 부모노드 다르면: (에지의 시작점과 끝점이 연결되어 있으므로 부모노드가 같으면 안됨)
		union연산 수행
		에지 가중치 정답에 더하기
	현재 에지수 +1

최소 신장 트리의 가중치 출력
		

3. 코드

#1197
#https://www.acmicpc.net/problem/1197

import sys
input = sys.stdin.readline
from queue import PriorityQueue

V, E = map(int, input().split())
que = PriorityQueue()
parent = [0]*(V+1) #부모 리스트
#union으로 부모노드 찾아가기
for i in range(1, V+1):
    parent[i] = i

for i in range(E):
    a, b, c = map(int, input().split())
    que.put((c,a,b)) #에지리스트
#union-find
def find(a):
    if parent[a] == a: #자신의 부모노드가 자기자신
        return a
    else:
        parent[a] = find(parent[a]) #자신의 부모노드 찾기 - 자기자신이 부모노드인 노드를 찾을때까지 계속 실행
        #재귀함수를 다시돌아오면서 거쳤던 노드의 부모노드를 다 재설정해주기
        return parent[a]

def union(a,b):
    parent_a = find(a)
    parent_b = find(b)
    parent[parent_b] = parent_a #b의 부모노드의 부모를 - a의 부모노드로 설정하기

#최소신장트리
result = 0
edge = 0

while edge != (V-1):
    now_node = que.get() #(c,a,b)
    if find(now_node[1]) != find(now_node[2]): #입력된 결과에 따르면 a와 b는 연결된 노드이므로 연결해야됨
        #하지만 사이클이 있을 경우에는 시행해선 안됨
        union(now_node[1], now_node[2])
        result += now_node[0]
        edge+=1

print(result) #최소신장트리가 아닐땐 뭐를 출력?

4. 코드 후기

지금 매우 시간 부족 이슈로 코드 후기 작성 불가능
오늘 안에 최소신장트리, 트라이, 이진트리 끝내야됨
ㅈ됐노