BOJ 16398

17 Sep 2020 • ProblemSolving

행성연결

문제출처

문제 해석

N개의 행성을 모두 연결하기 위한 최소한의 유지비용을 찾는 문제입니다.

설계(5)

행성들을 모두 연결하되, 그 유지비용을 최소화시키는 방법을 찾기위해서 MST알고리즘을 사용합니다.

그 중, Kruscal알고리즘을 사용하였습니다.

여기서 주의할 점은 각 간선의 유지비용이 최대 10^8이므로 유지비용을 합할 때, 정수형의 범위를 초과할 수 있습니다.

따라서 long long 변수로 유지비용의 합을 구해야합니다.

구현(10)

코드
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>

using namespace std;

#define MAXN 1001
int N;
int arr[MAXN][MAXN];
int par[MAXN];
struct node {
	int u, v, w;
	bool operator < (const node& a)const {
		return w < a.w;
	}
};
vector<node> adj;
int Find(int x) {
	if (par[x] == -1) return x;
	return par[x] = Find(par[x]);
}
bool Merge(int u, int v) {
	u = Find(u);
	v = Find(v);
	if (u == v) return false;
	par[u] = v;
	return true;
}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	memset(par, -1, sizeof(par));
	cin >> N;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			cin >> arr[i][j];
			if (i < j) {
				adj.push_back({ i,j,arr[i][j] });
			}
		}
	}
	sort(adj.begin(), adj.end());
	long long ans = 0;
	for (int i = 0; i < adj.size(); i++) {
		if (Merge(adj[i].u, adj[i].v)) ans += (long long)adj[i].w;
	}
	cout << ans << "\n";
	return 0;
}


def Find(x):
    if par[x]==-1: return x
    p =Find(par[x])
    par[x] = p
    return p

def Merge(u, v):
    u = Find(u)
    v = Find(v)
    if u==v: return False
    par[u] = v
    return True
N = int(input())
arr = [[int(x) for x in input().split()] for y in range(N)]
adj = list()
par = [-1]*N
for x in range(N):
    for y in range(x+1,N):
        adj.append(tuple([arr[x][y],x,y]))

adj.sort()
ans = 0
for w,u,v in tuple(adj):
    if (Merge(u,v)==True):
        ans+= w
print(ans)
디버깅

long long형 변수를 사용하지 않고 int 형 변수를 사용하는 실수를 하였습니다.

제출결과

c++ : 176 ms pypy3 : 2456 ms

마무리

python 언어 구사 능력을 기르기 위해서 c++과 python 두개의 언어로 모두 구현하고자 합니다.

해당 문제는 MST의 기본적인 유형이었습니다.

 BOJ

Related Posts