[백준(BOJ)] 1922번 네트워크 연결 - 파이썬/python

문제

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

1922번: 네트워크 연결

컴퓨터와 컴퓨터를 모두 연결하는 네트워크를 구축하려고 할 때, 컴퓨터를 연결하는 비용을 최소로 하는 최소비용을 구하는 문제다.

예시

Example 1:

Input: 6
	9
	1 2 5
	1 3 4
	2 3 2
	2 4 7
	3 4 6
	3 5 11
	4 5 3
	4 6 8
	5 6 8
Output: 23

풀이

# prim
def prim(n, edges):
    """
        n: 정점의 개수
        edges: (정점1, 정점2, 가중치)의 리스트

        최소 스패닝 트리의 가중치를 반환
    """
    import heapq

    graph = [[] for _ in range(n + 1)]
    for idx, adj, cost in edges:
        graph[idx].append((cost, adj))
        graph[adj].append((cost, idx))

    visited = [False] * (n + 1)
    visited[1] = True
    heap = []
    for cost, adj in graph[1]:
        heapq.heappush(heap, (cost, adj))

    result = 0
    used_edges = 0
    while used_edges < n - 1:
        cost, idx = heapq.heappop(heap)
        if visited[idx]:
            continue
        visited[idx] = True
        result += cost
        used_edges += 1
        for adj_cost, adj in graph[idx]:
            if not visited[adj]:
                heapq.heappush(heap, (adj_cost, adj))

    return result


if __name__ == '__main__':
    import sys
    input = sys.stdin.readline
    n = int(input())
    m = int(input())
    edges = [tuple(map(int, input().split())) for _ in range(m)]
    print(prim(n, edges))

 

# kruskal
class DisjointSet:

    def __init__(self, n):
        self.parent = list(range(n + 1))

    def find(self, x):
        if self.parent[x] == x:
            return x
        self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

    def union(self, x, y):
        root_x = self.find(x)
        root_y = self.find(y)
        if root_x == root_y:
            return
        self.parent[root_x] = root_y

if __name__ == '__main__':
    import sys
    input = sys.stdin.readline
    n = int(input())
    m = int(input())
    """
        n: 정점의 개수
        edges: (정점1, 정점2, 가중치)의 리스트
    """
    edges = [tuple(map(int, input().split())) for _ in range(m)]
    # 간선을 가중치 낮은 순으로 정렬
    edges.sort(key=lambda x: x[2])
    disjoint_set = DisjointSet(n)
    result = 0
    used_edges = 0

    for idx, adj, cost in edges:
        # 각 노드의 부모 노트 탐색, 사이클이 생기지 않는다면 간선 선택. 
        # 부모 노드가 같다 = 이 간선을 선택하면 사이클이 생긴다.
        if disjoint_set.find(idx) != disjoint_set.find(adj):
            disjoint_set.union(idx, adj)
            result += cost
            used_edges += 1
            if used_edges == n - 1:
                break
    print(result)

 

- 주어진 컴퓨터를 모두 연결하면서 연결하는 비용이 최소가 되어야 하므로 최소 신장 트리 알고리즘을 사용하여 풀 수 있다.