184. 네트워크

백준

1. Python

크루스칼 알고리즘

n = int(input())
m = int(input())
parent = [i for i in range(n + 1)]
edges = []


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

def union(a,b):
  a = find(a)
  b = find(b)
  if not a == b:
    parent[b] = a

def check(a,b):
  if find(a) == find(b):
    return True
  else:
    return False

for _ in range(m):
  a, b, cost = map(int, input().split())
  edges.append((cost, a, b))

edges.sort()

result = 0

for edge in edges:
  cost, a, b = edge
  if not check(a, b):
    union(a, b)
    result += cost

print(result)

프림 알고리즘

import sys
import heapq

def prim(v):
    q = []
    mst[v] = 1
    result = 0
    for i in adj[v]:
        heapq.heappush(q, i)

    while q:
        c, v = heapq.heappop(q)
        if not mst[v]:
            mst[v] = 1
            result += c
            for j in adj[v]:
                heapq.heappush(q, j)
        if sum(mst) == n:
            return result

input = sys.stdin.readline
n = int(input())
m = int(input())
adj = [[] for _ in range(n+1)]
mst = [0]*(n+1)
for _ in range(m):
    a, b, c = map(int, input().split())
    adj[a].append([c, b])
    adj[b].append([c, a])

print(prim(1))

2. C++

크루스칼 알고리즘

#include<iostream>
#include<vector>
#include<algorithm>
#define MAX 0x7fff0000
#define N_ 100000
using namespace std; 
 
int n, m, par[N_], ans; 
vector<pair<int, pair<int, int>>> v; 
 
int find(int x) {
    if (x == par[x])
        return x; 
    return par[x] = find(par[x]); 
}
 
bool Merge(int x, int y) {
    x = find(x); 
    y = find(y); 
    if (x == y)
        return false; 
    par[y] = x; 
    return true; 
}
 
int main() {
    int v1, v2, w;
    ios::sync_with_stdio(false); 
    cin.tie(NULL); 
    cout.tie(NULL);   
 
    cin >> n >> m; 
    for (int i = 1; i <= n; i++)
        par[i] = i; 
    
    while (m--) {
        cin >> v1 >> v2 >> w; 
        v.push_back({ w, {v1, v2}}); 
    }
    sort(v.begin(), v.end());    // 가중치 별 정렬 
    
    for (int i = 0; i < v.size(); i++) {
        int w = v[i].first; 
        int v1 = v[i].second.first; 
        int v2 = v[i].second.second; 
        if (Merge(v1, v2))  // 사이클 발생하지 않을경우 연결 후  
            ans += w;    // 연결비용 적재 
    }
    cout << ans; 
    return 0; 
}

프림 알고리즘

#include <iostream>
#include <queue>
#include <vector>
#include <cstring>
#include <functional>
using namespace std;
const int INF = 2000000000;
int n, m;
vector <pair<int, int>> vec[1001];
vector <pair<int, int>> selected;
bool visited[1001] = { 0, };

int result = 0;
void prim() {

	priority_queue <pair<int, int>> pq;
	for (int i = 0; i < vec[1].size(); i++) {
		int to = vec[1][i].first;
		int co = vec[1][i].second;
		pq.push(make_pair(-1 * co, to));
	}

	visited[1] = 1;
	while (!pq.empty()) {
		int co = pq.top().first * -1;
		int to = pq.top().second;
		pq.pop();

		if (visited[to] == false) {

			visited[to] = true;
			result += co;

			for (int i = 0; i < vec[to].size(); i++) {
				int nto = vec[to][i].first;
				int nco = vec[to][i].second;

				if(visited[nto] == false)
					pq.push(make_pair(-1 * nco, nto));
			}
		}



	}

}


int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	cin >> n;
	cin >> m;

	int from, to, cost;
	for (int i = 0; i < m; i++) {
		cin >> from >> to >> cost;
		vec[from].push_back(make_pair(to, cost));
		vec[to].push_back(make_pair(from, cost));
	}

	prim();
	
	cout << result << endl;

	return 0;
}