Notice
Recent Posts
Recent Comments
Link
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | 7 |
8 | 9 | 10 | 11 | 12 | 13 | 14 |
15 | 16 | 17 | 18 | 19 | 20 | 21 |
22 | 23 | 24 | 25 | 26 | 27 | 28 |
29 | 30 | 31 |
Tags
- JUnit 5
- BFS
- 동적계획법
- Network
- 위상정렬
- 수학
- 백준
- 그리디
- CS
- 백트래킹
- 에라토스테네스의 체
- 문자열
- 후니의 쉽게 쓴 시스코 네트워킹
- 구현
- Effective Java
- java
- 알고리즘
- Kotlin
- 완전탐색
- swea
- dfs
- 이분탐색
- 유니온 파인드
- 플로이드-와샬
- 세그먼트 트리
- 시뮬레이션
- 스택
- 프로그래머스
- 투 포인터
- mst
Archives
반갑습니다!
[백준] 1647 도시 분할 계획 본문
풀이
이 문제는 최소한의 비용으로 두 마을을 만들어야하는데, 결국 1개의 최소 스패닝 트리를 만들고 그 중에 가장 큰 간선을 제거해주면 최소한의 비용으로 2개의 마을을 만든 것과 같다. 크루스칼 알고리즘을 사용해서 최소 스패닝 트리를 만들어서 해결하였다.
코드
C++
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int n, m;
vector<pair<int, pair<int, int>>> edges;
vector<int> root;
int find(int v) {
if (root[v] != v)
root[v] = find(root[v]);
return root[v];
}
void merge(int a, int b) {
a = find(a);
b = find(b);
if (a < b)
root[b] = a;
else
root[a] = b;
}
int kruskal() {
int last = 0;
int sum = 0;
for (int i = 0; i < edges.size(); i++) {
int a = edges[i].second.first;
int b = edges[i].second.second;
int c = edges[i].first;
if (find(a) == find(b)) continue;
merge(a, b);
sum += c;
last = c;
}
return sum - last;
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> n >> m;
root = vector<int>(n + 1);
for (int i = 1; i <= n; i++)
root[i] = i;
for (int i = 0; i < m; i++) {
int a, b, c;
cin >> a >> b >> c;
edges.push_back({ c, {a, b} });
}
sort(edges.begin(), edges.end());
cout << kruskal() << '\n';
return 0;
}
Python3
import sys
def find(x):
if root[x] != x:
root[x] = find(root[x])
return root[x]
def union(a, b):
a = find(a)
b = find(b)
if a < b:
root[b] = a
else:
root[a] = b
def kruskal():
sum = 0
last = 0
for i in edges:
c, a, b = i
if find(a) == find(b):
continue
union(a, b)
sum += c
last = c
return sum - last
n, m = map(int, sys.stdin.readline().rstrip().split())
root = [0 for _ in range(n + 1)]
edges = []
for i in range(1, n + 1):
root[i] = i
for _ in range(m):
a, b, c = map(int, sys.stdin.readline().rstrip().split())
edges.append((c, a, b))
edges.sort()
print(kruskal())
'알고리즘 문제 풀이' 카테고리의 다른 글
[백준] 3665 최종 순위 (0) | 2020.10.06 |
---|---|
[백준] 2887 행성 터널 (0) | 2020.10.06 |
[백준] 15809 전국시대 (0) | 2020.10.06 |
[백준] 2153 소수 단어 (0) | 2020.10.05 |
[백준] 3986 좋은 단어 (0) | 2020.10.05 |