💬 문제 요약

1922번 네트워크연결
모든 컴퓨터를 연결하는데 필요한 최소비용

🤔 보고 든 생각

어 완전 신장 트리를 연결하는 최소 비용구하기 = 크루스칼 그 자체 구만
정리해뒀던 그래프-크루스칼알고리즘 에 있는 구현코드대로 만들면 되겠구만
이런문제들만 나왔으면 좋겠다 헤헤..

🗡 첫번재 시도

# 특정 원소가 속한 집합 찾기 
def find_parent(parent, x) :
	# 루트노드가 아니라면, 루트노드를 찾을때까지 재귀호출
  if parent[x] != x :
    parent[x] = find_parent(parent, parent[x])
  return parent[x]

        
# 두 원소가 속한 집합 합치기
def union_parent(parent, a, b) :
  a = find_parent(parent, a)
  b = find_parent(parent, b)
  
  if a < b :
    parent[b] = a
  else :
    parent[a] = b

# 노드의 갯수와 간선(union 연산)의 갯수 입력받기
v = int(input())
e = int(input())
parent = [0] * (v+1) #부모 테이블 초기화


# 모든 간선을 담을 리스트와 최종 비용을 담을 변수 
edges = []
result = 0

# 부모 테이블상에서, 부모를 자기자신으로 초기화
for i in range(1, v+1) :
	parent[i] = i

# 모든 간선에 대한 정보를 입력받기
for _ in range(e) :
  a, b, cost = map(int, input().split())
  # 비용순으로 정렬하기 위해서 튜플의 첫번째 원소를 비용으로 설정
  edges.append((cost, a, b))

# 간선을 비용순으로 정렬
edges.sort()

# 간선을 하나씩 확인하며
for edge in edges :
  cost, a, b = edge
    # 사이클이 발생하지 않는 경우에만 집합에 포함
  if find_parent(parent, a) != find_parent(parent, b) :
    union_parent(parent, a, b)
    result += cost
 
print(result) # 최종 최소 비용을 출력

통과!!👻

다음에는 정리해뒀던 코드 보고 안보고 외워서 짜보자!