[백준 1922] 네트워크 연결

문제

N대의 컴퓨터를 모두 연결하는 네트워크를 구축하려고 한다. 이때 각각의 컴퓨터를 연결하는데 비용이 들기 때문에 N대의 컴퓨터를 연결하는데 드는 최소 비용을 구하라.

A->B이고 B->C이면 A->C가 된다고 한다.

 

입력

첫째 줄에 컴퓨터의 수 N (1 ≤ N ≤ 1000)가 주어진다.

둘째 줄에는 연결할 수 있는 선의 수 M (1 ≤ M ≤ 100,000)가 주어진다.

셋째 줄부터 M+2번째 줄까지 총 M개의 줄에 각 컴퓨터를 연결하는데 드는 비용이 주어진다. 이 비용의 정보는 세 개의 정수로 주어지는데, 만약에 a b c 가 주어져 있다고 하면 a컴퓨터와 b컴퓨터를 연결하는데 비용이 c (1 ≤ c ≤ 10,000) 만큼 든다는 것을 의미한다. a와 b는 같을 수도 있다.

 

출력

모든 컴퓨터를 연결하는데 필요한 최소비용을 첫째 줄에 출력한다.

---

접근

모든 컴퓨터를 연결할 수 있는 경우의 수가 많을 수 있다. 이 중에서 연결비용을 따져서 최소비용으로 연결을 해야한다.

여기서 모든 컴퓨터를 연결할 때 최소비용을 구해야한다고 했기 때문에 최소신장트리를 구성해야하고, 이를 위해 크루스칼 알고리즘을 사용하고자 했다.

 

구현

A->B의 연결비용인 C를 기준으로 오름차순으로 정렬하고 N-1개의 연결을 선택하도록한다.

입력받은 a, b, c를 graph라는 리스트에 넣는다.

for _ in range(M):
    a, b, c = map(int, input().split())
    a -= 1
    b -= 1
    graph.append((a, b, c))

 

이제 연결비용을 기준으로 오름차순으로 정렬한다.

graph = sorted(graph, key=lambda x: x[2])

 

- 이제 edge_count(연결 수)가 N-1이 될 때까지 연결을 선택한다.

- a와 b가 다른 루트노드라면 연결이 가능하고 a와 b를 이후에 합쳐준다.

- 여기서 최종해에 c를 더해주고 연결 수를 1증가시킨다.

edge_count = 0
answer = 0
for a, b, c in graph:
    if find_set(a) != find_set(b):
        union(a, b)
        edge_count += 1
        answer += c
    if edge_count == N-1:
        break

---

전체 코드

import sys
input = sys.stdin.readline

def find_set(a):
    if p[a] == a:
        return a
    else:
        b = find_set(p[a])
        p[a] = b
        return b

def union(a, b):
    a = find_set(a)
    b = find_set(b)
    if a != b:
        p[b] = a

N = int(input())
M = int(input())
p = [n for n in range(N)]
graph = []

for _ in range(M):
    a, b, c = map(int, input().split())
    a -= 1
    b -= 1
    graph.append((a, b, c))

graph = sorted(graph, key=lambda x: x[2])

edge_count = 0
answer = 0
for a, b, c in graph:
    if find_set(a) != find_set(b):
        union(a, b)
        edge_count += 1
        answer += c
    if edge_count == N-1:
        break

print(answer)