[백준] 10423번 전기가 부족해(Java) - 세무민의 코딩일기

이번 포스팅에서 풀어본 문제는 "전기가 부족해"라는 문제입니다.

---

1. 문제 

---

2. 입출력 및 예제 

---

3. 문제 풀이 

이번 문제는 가장 중요한 것이 3개의 발전소로 나눈다는 것이다.

따라서 이번 문제에서는 find를 이용하여 정점들을 탐색할 때 탐색한 경우 체크하는 것이 중요하다 .

아래의 그림을 통해서 이해해보자

위의 그림처럼 가정하여 풀어보도록 하자.

처음에는 발전소를 선택하지 않았기 때문에 모두 0의 값을 가진다.

발전소를 1,2,9번으로 선택하고 진행할 예정이다.

발전소를 선택했을 때 해당 발전소의 값(index)에는 체크를 해두면 된다. 

양수의 값의 경우 겹칠 수 있기 때문에 음수의 값으로 체크하는 것이 중요하다.(boolean으로도 가능)

가장 짧은 간선인 2를 이어주고 7에 체크를 해준다.

다음으로 짧은 간선인 3을 이어주고 3에 체크를 해준다.

위에 처럼 가장 짧은 간선인 4를 연결해주며 5와 6, 그리고 8에 체크를 해준다.

마지막으로 간선 4를 가진 정점 4에 체크를 해주면 모든 정점들을 다 연결하게 되었다. 

아래처럼 보면 1개 이상의 정점들로 구성되어 있기 때문에 발전소를 3개로 나눌 수 있다. 

즉 위의 그림처럼 발전소를 체크하여 최소 신장 트리를 진행하는 것이 중요한 문제이다.

---

4. 코드

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);
		
		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();
		
		
		
		
		
	}

}

코드는 위와 같으며 결론적으로는 탐색하되 최소값을 반환해주면 된다.

코드는 위의 그림처럼 모든 정점들을 탐색하면서 -1로 연결하여 최종적으로 모든 정점들을 연결하게 된다. 

👉👉 GitHub

GitHub - sg-moomin/programmersStudy

상세한 코드는 GitHub에 동일하게 구성되어 있습니다. 

결과는 성공입니다.

---

이번 포스팅에서도 Kruskal-Mst 알고리즘을 풀어봤습니다.

다음에도 더 좋은 포스팅으로 찾아오도록 하겠습니다.