네트워크 연결 [백준 1922] - python

import sys
input = sys.stdin.readline

def BOJ1922() :
  N = int(input())
  M = int(input())
  # 각 node에서 처음 부모는 자신 node들 입니다
  parent = [i for i in range(N+1)]
  

  def find_parent(x):
    if (x == parent[x]):
      return x
    else:
      y = find_parent(parent[x])
      parent[x] = y
      return y

  def union_parent(a, b) :
    parent_a = find_parent(a)
    parent_b = find_parent(b)
    if parent_a > parent_b :
      parent[parent_b] = parent_a
    else :
      parent[parent_a] = parent_b

  l = []
  for _ in range(M) :
    l.append(list(map(int, input().split())))
  l.sort(key = lambda x : x[2])
  
  result = 0
  
  for node in l : 
    a, b, cost = node
    
    if find_parent(a) != find_parent(b) :
      union_parent(a, b)
      result += cost
  
  print(result)

BOJ1922()

 

 해당 문제는 풀지 못하였고 다른 분들의 풀이를 참고하였습니다. ㅜㅜ

 

접근 방법 : 

1. 해당 문제는 최소 신장 트리의 개념을 이용해야 합니다.

또한 최소 신장 트리를 구현하기위해 Kruskal 알고리즘을 적용하여야 합니다.

kruskal 알고리즘을 적용하기 위해서 union_find 알고리즘을 이용해야 합니다.

 

최소 신장 트리(Minimum Spanning Tree)

최소신장트리를 알기전에 신장트리(spanning Tree)를 먼저 알아보고 가겠습니다.

 

신장트리 => 그래프 내의 모든 정점을 포함하는 트리입니다.

하나의 그래프에서 여러개의 신장트리가 존재할 수 있습니다.

 

사이클을 포함해서는 안됩니다!

정점이 n개 이면 간선은 n-1개가 됩니다. => 모든 정점들을 연결해야 하기 때문!

 

이렇게 구성되는 여러가지 신장 트리중 비용이 가장 적은 신장트리가 최소 신장 트리가 됩니다!!

 

최소 신장 트리는 대표적으로 네트워크를 구축할 때 사용합니다.

저 간선들은 길면 길수록 돈이 많이 깨지기 때문에 길이는 최대한 짧아야 겠지요???

 

 

Kruskal 알고리즘

그리디(greedy)를 이용하여 스패닝 트리의 최소의 비용을 구하는 알고리즘 입니다.

구현과정은 문제에 주어진 것을 기준으로 설명하겠습니다

1. 우선 비용들에 대한 정보를 오름차순으로 정렬해 줍니다.

2. 비용이 작은 간선부터 하나씩 업데이트를 해줍니다.

다음 차례인 1 2 5 는 이미 선택된 간선들과 사이클을 이루게 되므로 선택하지 못합니다.

5 6 8 과 3 5 11 또한 이미 선택된 간선들과 사이클을 이루게 되므로 선택하지 못합니다.

 

그리디한 방법으로 하나씩 간선을 선택해 나가는 것

사이클을 이루는 간선은 선택하지 않는 것이 최소신장트리를 구하기 위한 kruskal 알고리즘의 개념입니다.

 

사이클을 이루는 지 검토하는 방법은 추가하고자 하는 간선의 양끝 지점이 같은 집합에 속해있는지를 체크해야 합니다.

이 같은 집합에 속해있는지 판단할때 union_find 알고리즘을 이용하게 됩니다.

 

Union_find 알고리즘

이름을 먼저 살펴보겠습니다.

 

union: 두개의 집합을 하나의 집합으로 합친다.

find: 어떤 원소가 주어졌을때 이 원소가 속한 집합을 반환한다

 

유니온 연산을 여러번 하게 되면 여러 집합들은 합쳐지게 됩니다.

# 입력받은 node에서 부모를 찾는 함수
  def find_parent(x):               
    if (x == parent[x]):
      return x
    else:
      y = find_parent(parent[x])
      parent[x] = y
      return y

# 입력받은 node들의 부모를 찾고 같지 않으면 서로 union 하는 함수
  def union_parent(a, b) :
    parent_a = find_parent(a)
    parent_b = find_parent(b)
    if parent_a > parent_b :
      parent[parent_b] = parent_a
    else :
      parent[parent_a] = parent_b

 

 

2. 전체 node들을 순회하면서 각각의 집합들을 부모가 같아질때까지 union 해주면 최소신장트리의 비용을 구할 수 있습니다

 

 

 

 

https://www.acmicpc.net/problem/1922

1922번: 네트워크 연결

 

출처 :

https://gmlwjd9405.github.io/2018/08/28/algorithm-mst.html

[알고리즘] 최소 신장 트리(MST, Minimum Spanning Tree)란 - Heee's Development Blog

 

https://gmlwjd9405.github.io/2018/08/29/algorithm-kruskal-mst.html

[알고리즘] Kruskal 알고리즘 이란 - Heee's Development Blog

https://ko.wikipedia.org/wiki/%EC%84%9C%EB%A1%9C%EC%86%8C_%EC%A7%91%ED%95%A9_%EC%9E%90%EB%A3%8C_%EA%B5%AC%EC%A1%B0

서로소 집합 자료 구조 - 위키백과, 우리 모두의 백과사전