-
Notifications
You must be signed in to change notification settings - Fork 0
/
backjoon_10423.java
152 lines (110 loc) · 3.04 KB
/
backjoon_10423.java
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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
package backjoon_20211003;
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.Collections;
import java.util.StringTokenizer;
/**
* [전기가 부족해]
* Q. 3개의 발전소를 기준으로 도시를 연결한다.
* Q. 3개의 발전소를 먼저 체크한 뒤 동일하게 kruskal을 이용하여 연결한다.
* Q. 마지막 남은 노드를 연결하는 선을 제외하는 방식이다.
*
*
* */
class city implements Comparable<city>{
int fristNode;
int endNode;
int result;
city(int fristNode, int endNode, int result){
this.fristNode = fristNode;
this.endNode = endNode;
this.result = result;
}
@Override
public int compareTo(city o) {
return result - o.result;
}
}
public class backjoon_10423 {
static int[] parent;
static int[] ynyCity;
static ArrayList<city> Nodes;
public static int find(int answer) {
if(parent[answer] == -1) {
return -1;
}
if(parent[answer] == answer) {
return answer;
} else {
return parent[answer] = find(parent[answer]);
}
}
public static void union(int x, int y) {
x = find(x);
y = find(y);
if(x == -1){
parent[y] = x;
} else if(y == -1) {
parent[x] = y;
}
else if(y != x) {
parent[y] = x;
}
}
public static int kruskal(int m) {
parent = new int[m + 1];
for(int i = 1; i <= m; i++) {
if(ynyCity[i] == -1) {
parent[i] = -1;
} else {
parent[i] = i;
}
}
Collections.sort(Nodes);
for(int i = 0; i < Nodes.size(); i++) {
System.out.println("node arr : " + Nodes.get(i).fristNode + " | " + Nodes.get(i).endNode + " | " + Nodes.get(i).result);
}
int answer = 0;
for(city node : Nodes) {
city cityNode = node;
if(find(cityNode.fristNode) != find(cityNode.endNode)) {
union(cityNode.fristNode, cityNode.endNode);
answer += cityNode.result;
}
}
return answer;
}
public static void main(String[] args) throws IOException {
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer stringTk;
stringTk = new StringTokenizer(reader.readLine());
int N = Integer.parseInt(stringTk.nextToken());
int M = Integer.parseInt(stringTk.nextToken());
int K = Integer.parseInt(stringTk.nextToken());
ynyCity = new int[N+1];
String cityCheck = reader.readLine();
stringTk = new StringTokenizer(cityCheck);
Nodes = new ArrayList<city>();
for(int i = 1; i <= K; i++) {
int num = Integer.parseInt(stringTk.nextToken());
ynyCity[num] = -1;
}
for(int i = 0; i < M; i++) {
stringTk = new StringTokenizer(reader.readLine());
int u = Integer.parseInt(stringTk.nextToken());
int v = Integer.parseInt(stringTk.nextToken());
int w = Integer.parseInt(stringTk.nextToken());
Nodes.add(new city(u, v, w));
}
int result = kruskal(N);
writer.write(result + "\n");
writer.flush();
writer.close();
reader.close();
}
}