
문제
마을은 N개의 집과 그 집들을 연결하는 M개의 길로 이루어져 있다. 길은 어느 방향으로든지 다닐 수 있는 편리한 길이다. 그리고 각 길마다 길을 유지하는데 드는 유지비가 있다.
마을의 이장은 마을을 두 개의 분리된 마을로 분할할 계획을 가지고 있다. 마을이 너무 커서 혼자서는 관리할 수 없기 때문이다. 마을을 분할할 때는 각 분리된 마을 안에 집들이 서로 연결되도록 분할해야 한다. 각 분리된 마을 안에 있는 임의의 두 집 사이에 경로가 항상 존재해야 한다는 뜻이다. 마을에는 집이 하나 이상 있어야 한다.
그렇게 마을의 이장은 계획을 세우다가 마을 안에 길이 너무 많다는 생각을 하게 되었다. 일단 분리된 두 마을 사이에 있는 길들은 필요가 없으므로 없앨 수 있다. 그리고 각 분리된 마을 안에서도 임의의 두 집 사이에 경로가 항상 존재하게 하면서 길을 더 없앨 수 있다. 마을의 이장은 위 조건을 만족하도록 길들을 모두 없애고 나머지 길의 유지비의 합을 최소로 하고 싶다. 이것을 구하는 프로그램을 작성하시오.
1647번: 도시 분할 계획
첫째 줄에 집의 개수 N, 길의 개수 M이 주어진다. N은 2이상 100,000이하인 정수이고, M은 1이상 1,000,000이하인 정수이다. 그 다음 줄부터 M줄에 걸쳐 길의 정보가 A B C 세 개의 정수로 주어지는데 A번
www.acmicpc.net
문제조건
첫째 줄에 집의 개수 N, 길의 개수 M이 주어진다. N은 2이상 100,000이하인 정수이고, M은 1이상 1,000,000이하인 정수이다. 그 다음 줄부터 M줄에 걸쳐 길의 정보가 A B C 세 개의 정수로 주어지는데 A번 집과 B번 집을 연결하는 길의 유지비가 C (1 ≤ C ≤ 1,000)라는 뜻이다.
풀이
MST를 구하는 문제. 크루스칼 알고리즘을 사용하여 구할 수 있다. 사이클인지 확인하기 위해서 union-find 알고리즘을 사용하였다. 두 마을로 나뉘어야 한다는 조건은 MST에서 간선 한개를 지워주는 식으로 구할 수 있다. 길 유지비를 최소로 하기 위해 가장 마지막(가장 큰) 간선을 지워주었다.
MST를 구하는 문제는 학교에서 알고리즘 시간 이후로 처음 접하는 것 같다. 증명도 하고 했었는데 기억이 하나도 안난다
코드
#include <iostream> #include <algorithm> #include <vector> using namespace std; #define MAX 100000 + 1 int N, M; vector <pair <int, pair <int, int>>> edge; int parent[MAX]; vector <int> v; int findParent(int x) { if (x == parent[x]) return x; else return parent[x] = findParent(parent[x]); } void union(int x, int y) { x = findParent(x); y = findParent(y); if (x == y) return; parent[y] = x; } int main() { cin >> N >> M; for (int i = 0; i < M; i++) { int a, b, c; cin >> a >> b >> c; edge.push_back({ c,{ a,b } }); } sort(edge.begin(), edge.end()); //edge값에 대해서 오름차순으로 정렬 // root 초기화(자기자신으로) for (int i = 1; i <= N; i++) { parent[i] = i; } // 크루스칼 알고리즘 for (int i = 0; i < edge.size(); i++) { int s = edge[i].second.first; int e = edge[i].second.second; if (findParent(s) != findParent(e)) { union(s, e); v.push_back(edge[i].first); } } int ans = 0; for (int i = 0; i < v.size() - 1; i++) { ans += v[i]; } cout << ans; }
'알고리즘 > BOJ' 카테고리의 다른 글
[백준] 7579번: 앱 (c++) (0) | 2021.09.30 |
---|---|
[백준] 1202번: 보석 도둑 (c++) (0) | 2021.09.29 |
[백준] 17143번: 낚시왕 (c++) (0) | 2021.09.27 |
[백준] 9466번: 텀 프로젝트 (c++) (0) | 2021.09.23 |
[백준] 10942번: 팰린드롬? (c++) (0) | 2021.09.22 |