https://www.acmicpc.net/problem/21924
21924번: 도시 건설
첫 번째 줄에 건물의 개수 $N$ $(3 \le N \le 10^5 )$와 도로의 개수 $M$ $(2 \le M \le min( {N(N-1) \over 2}, 5×10^5)) $가 주어진다. 두 번째 줄 부터 $M + 1$줄까지 건물의 번호 $a$, $b$ $(1 \le a, b \le N, a ≠ b)$와 두
www.acmicpc.net
코드설명
전형적인 크루스칼 알고리즘입니다.
다만, 한가지 유의해야할점은
- 만약 모든 건물이 연결되어 있지 않는다면 -1을 출력한다.
모든 건물이 연결되어있다면, findParent를 진행하였을때 모두 같은 집합에 속해야만 합니다. (문제에서 가장 중요한점 )
for(int i=1;i<N;i++) {
if( findParent(i) != findParent(i+1)) {
System.out.println("-1");
return ;
}
}
unionFind 알고리즘에 의하여 각 노드의 parent가 업데이트 되지 않는 경우가 있기에
모든 노드를 돌면서 findParent를 통해서 parent를 직접 다시 한번 체크해줘야합니다.
코드
BufferedReader활용하여 시간단축
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.StringTokenizer;
public class Main {
public static int N,M;
public static int[] parent = new int[100001];
public static ArrayList<Edge> edges = new ArrayList<>();
public static long result = 0;
public static long wholecost = 0;
public static int count = 0;
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
for(int i=0;i<=N;i++) {
parent[i] = i;
}
for(int j=0;j<M;j++) {
st = new StringTokenizer(br.readLine());
int a = Integer.parseInt(st.nextToken());
int b = Integer.parseInt(st.nextToken());
int cost = Integer.parseInt(st.nextToken());
edges.add(new Edge(a, b, cost));
wholecost += cost;
}
Collections.sort(edges);
for(int i=0;i<edges.size();i++) {
int a = edges.get(i).nodeA;
int b = edges.get(i).nodeB;
int cost = edges.get(i).distance;
if( findParent(a) != findParent(b)) {
unionParent(a, b);
result += cost;
}
}
// for(int i=0;i<=N;i++) {
// System.out.println("FINDPARENT"+parent[i]);
// }
for(int i=1;i<N;i++) {
if( findParent(i) != findParent(i+1)) {
System.out.println("-1");
return ;
}
}
if(wholecost - result < 0) {
System.out.println("0");
}else {
System.out.println(wholecost - result);
}
}
//부모를 찾는다.
public static int findParent(int a) {
if( a == parent[a]) return a;
return parent[a] = findParent(parent[a]);
}
//
public static void unionParent(int a, int b) {
a = findParent(a);
b = findParent(b);
if( a < b ) parent[b] = a;
else parent[a] = b;
}
}
class Edge implements Comparable<Edge>{
int nodeA;
int nodeB;
int distance;
public Edge(int nodeA, int nodeB, int distance) {
this.nodeA = nodeA;
this.nodeB = nodeB;
this.distance = distance;
}
//비용이 낮은것으로 정렬합니다.
@Override
public int compareTo(Edge other) {
if(this.distance > other.distance) {
return 1;
}else if(this.distance < other.distance) {
return -1;
}
return 0;
}
}
import java.util.*;
public class Main {
public static int N,M;
public static int[] parent = new int[100001];
public static ArrayList<Edge> edges = new ArrayList<>();
public static long result = 0;
public static long wholecost = 0;
public static int count = 0;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
N = sc.nextInt();
M = sc.nextInt();
for(int i=0;i<=N;i++) {
parent[i] = i;
}
for(int j=0;j<M;j++) {
int a = sc.nextInt();
int b = sc.nextInt();
int cost = sc.nextInt();
edges.add(new Edge(a, b, cost));
wholecost += cost;
}
Collections.sort(edges);
for(int i=0;i<edges.size();i++) {
int a = edges.get(i).nodeA;
int b = edges.get(i).nodeB;
int cost = edges.get(i).distance;
if( findParent(a) != findParent(b)) {
unionParent(a, b);
result += cost;
}
}
// for(int i=0;i<=N;i++) {
// System.out.println("FINDPARENT"+parent[i]);
// }
for(int i=1;i<N;i++) {
if( findParent(i) != findParent(i+1)) {
System.out.println("-1");
return ;
}
}
if(wholecost - result < 0) {
System.out.println("0");
}else {
System.out.println(wholecost - result);
}
}
public static int findParent(int x) {
if( x == parent[x]) return x;
return parent[x] = findParent(parent[x]);
}
public static void unionParent(int a, int b) {
a = findParent(a);
b = findParent(b);
if( a < b ) parent[b] = a;
else parent[a] = b;
}
}
class Edge implements Comparable<Edge>{
int nodeA;
int nodeB;
int distance;
public Edge(int nodeA, int nodeB, int distance) {
this.nodeA = nodeA;
this.nodeB = nodeB;
this.distance = distance;
}
//최소비용순으로 정렬합니다.
@Override
public int compareTo(Edge other) {
if(this.distance < other.distance) {
return -1;
}else if(this.distance > other.distance){
return 1;
}else {
return 0;
}
}
}