Kruskal
public class Main {//Kruskal
static int N,M,K;//도시 개수 N, 케이블 설치 가능 개수 M, 발전소 개수 K
static int[] parent;//사이클 확인
static boolean[] check;//발전소 연결 확인
static boolean[][] cable;//케이블 연결된 도시 체크
static int city;
static class Distance implements Comparable<Distance>{
int s, e, d;
Distance(int s, int e, int d){
this.s = s;
this.e = e;
this.d = d;
}
@Override
public int compareTo(Distance dis) {
return Integer.compare(this.d, dis.d);
}
}
static PriorityQueue<Distance> pq;
public static void main(String[] args) throws IOException {
//System.setIn(new FileInputStream("input/bj/10423_전기가부족해.txt"));
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine().trim(), " ");
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
K = Integer.parseInt(st.nextToken());
parent = new int[N+1];
check = new boolean[N+1];
cable = new boolean[N+1][N+1];
for(int i = 1; i < N+1; i++) {//부모노드 자기자신으로 설정
parent[i] = i;
}
String[] plant = br.readLine().trim().split(" ");
for(int i = 0; i < K; i++) {//발전소 도시 체크
check[Integer.parseInt(plant[i])] = true;
}
pq = new PriorityQueue<Distance>();
for(int i = 0; i < M; i++) {//도시끼리 케이블 설치 비용 저장
st = new StringTokenizer(br.readLine().trim(), " ");
int s = Integer.parseInt(st.nextToken());
int e = Integer.parseInt(st.nextToken());
int d = Integer.parseInt(st.nextToken());
pq.add(new Distance(s,e,d));
}
city = K;//발전소 연결 된 도시 개수
int answer = 0;
while(city < N) {//모든 도시가 발전소에 연결될때까지
Distance cur = pq.poll();
int sp = findSet(cur.s);
int ep = findSet(cur.e);
if(sp == ep) continue;//사이클 생성
if(check[sp] && check[ep]) continue;//이미 발전소 연결되어 있으면
parent[sp] = ep;
cable[cur.s][cur.e]= cable[cur.e][cur.s] = true;//케이블 설치 체크
answer += cur.d;
//sp와 ep 둘 중 한 그룹만 발전소 연결이 되어 있는 경우
if(check[sp]) {
dfs(cur.s);
}else if(check[ep]) {
dfs(cur.e);
}
}
System.out.println(answer);
}
private static void dfs(int sp) {
for(int i = 1; i < N+1; i++) {
if(!cable[sp][i]) continue;//케이블X
if(check[i]) continue;//발전소 이미 연결 되어 있음
check[i] = true;
city++;//발전소에 연결된 도시
dfs(i);
}
}
public static int findSet(int node) {
if(node == parent[node]) {
return node;
}
return parent[node] = findSet(parent[node]);
}
}
Prim
public class Main {//Prim
static int N,M,K;//도시 개수 N, 케이블 설치 가능 개수 M, 발전소 개수 K
static boolean[] check;//발전소 연결 확인
static int[][] cable;//케이블 연결된 도시 체크
static class City implements Comparable<City>{
int num, cost;
City(int num, int cost){
this.num = num;
this.cost = cost;
}
@Override
public int compareTo(City c) {
return Integer.compare(this.cost, c.cost);
}
}
public static void main(String[] args) throws IOException {
//System.setIn(new FileInputStream("input/bj/10423_전기가부족해.txt"));
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine().trim(), " ");
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
K = Integer.parseInt(st.nextToken());
check = new boolean[N+1];
cable = new int[N+1][N+1];
String[] plant = br.readLine().trim().split(" ");
for(int i = 0; i < M; i++) {//도시끼리 케이블 설치 비용 저장
st = new StringTokenizer(br.readLine().trim(), " ");
int s = Integer.parseInt(st.nextToken());
int e = Integer.parseInt(st.nextToken());
int d = Integer.parseInt(st.nextToken());
cable[s][e] = cable[e][s] = d;
}
City[] city = new City[N+1];//각 도시까지 최단거리 저장할 배열
for(int i = 1; i < N+1; i++) {
city[i] = new City(i, Integer.MAX_VALUE);//최초에 최대값으로 세팅
}
for(int i = 0; i < K; i++) {//발전소 도시 체크
int cur = Integer.parseInt(plant[i]);
city[cur].cost = 0;//발전소 도시는 cost 0
}
int cnt = 0;//발전소 연결 된 도시 개수
int answer = 0;//총 비용
while(cnt < N) {
int min = Integer.MAX_VALUE;
int idx = -1;
for(int i = 1; i < N+1; i++) {//최소 간선 찾기
if(check[i]) continue;//이미 발전소 연결됐으면 continue
if(city[i].cost < min) {
min = city[i].cost;
idx = i;
}
}
if(idx == -1) break;//더 이상 연결할 도시 없으면 break;
City cur = city[idx];
int next = cur.num;
check[next] = true;
cnt++;
answer += cur.cost;
for(int i = 1; i < N+1; i++) {//각 도시까지 최단거리 배열 갱신
if(cable[next][i] == 0) continue;
if(city[i].cost > cable[next][i]) {
city[i].cost = cable[next][i];
}
}
}
System.out.println(answer);
}
}