[백준] 6497 -전력난 (JAVA)

1. 소요시간 : 20분
2. 문제 사이트 : 백준
3. 문제 수준 : 골드 4
4. 문제 유형 : 그래프 이론, 최소 스패닝 트리
5. 다른 사람의 풀이를 참고 했는가 ? : X
6. 한 번 풀었다가 다시 푸는 문제인가 ? : X
7. 문제 링크 : https://www.acmicpc.net/problem/6497
8. 푼 날짜 : 2023.03.21

1. 사용한 자료구조 & 알고리즘

최소 스패닝 트리를 사용했다.
크루스칼 알고리즘과 프림 알고리즘 중에서 크루스칼 알고리즘을 사용했고, 그렇게 하기 위해서 Union & Find 개념을 이용했다.

2. 사고과정

문제를 보자마자 최소 스패닝 트리 문제라는 것을 알았다.

3. 풀이과정

크루스칼 알고리즘의 그대로를 이용했다.
1. sum 이라는 값에 모든 cost 를 더해준다.
2. 각각의 길을 cost 별로 오름차순 정렬한다.
3. 만약 node1과 node2 가 서로 연결되어 있지 않다면 union 한다.
4. union 할 때마다 sum에서 cost 값을 빼준다.
5. 최소 스패닝 트리의 특징 (노드 수가 n 개라면 연결된 간선은 n-1 개 라는 것을 이용해서 union 해줄 때마다 cnt 를 증가시켰고, cnt 가 n-1 개가 되면 break 해줬다.
6. 최종적으로 출력

4. 소스코드

import java.io.*;
import java.util.*;

class Node{
	int node1;
	int node2;
	int cost;
	Node(int node1,int node2,int cost){
		this.node1=node1;
		this.node2=node2;
		this.cost=cost;
	}
}
public class Main {
	static StringBuilder sb=new StringBuilder();
	
	static int parent[];
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;

		while(true) {
			st=new StringTokenizer(br.readLine());
			int m=Integer.parseInt(st.nextToken());
			int n=Integer.parseInt(st.nextToken());
			if(m==0&&n==0) break;
			parent=new int[m+1];
			for(int i=1;i<parent.length;i++)
				parent[i]=i;
			
			Node node[]=new Node[n];
			int sum=0;
			for(int i=0;i<n;i++) {
				st=new StringTokenizer(br.readLine());
				int node1=Integer.parseInt(st.nextToken());
				int node2=Integer.parseInt(st.nextToken());
				int cost=Integer.parseInt(st.nextToken());
				node[i]=new Node(node1,node2,cost);
				sum+=cost;
			}
			Arrays.sort(node,new Comparator<>() {
				@Override
				public int compare (Node n1,Node n2) {
					if(n1.cost>n2.cost)
						return 1;
					else if(n1.cost==n2.cost)
						return 0;
					else
						return -1;
				}
			});
			int cnt=0;
			for(int i=0;i<node.length;i++) {
				int node1=node[i].node1;
				int node2=node[i].node2;
				int cost=node[i].cost;
				if(find(node1)!=find(node2)) {
					union(node1,node2);
					sum-=cost;		
					cnt++;
				}
				if(cnt==m-1) break;
			
			}
			sb.append(sum+"\n");
			
			
		}
		
		System.out.println(sb);
		
		
		
	}
	public static void union(int node1,int node2) {
		node1=find(node1);
		node2=find(node2);
		if(node1>node2)
			parent[node1]=node2;
		else
			parent[node2]=node1;
		
	}
	public static int find(int node) {
		if(parent[node]==node)
			return node;
		else
			return find(parent[node]);
	}
}

5. 결과

처음에 컴파일 에러가 나서 많이 당황했다. Arrays.sort 를 할 때 new Comparator<>()를 해주는 과정에서 오류가 났다고 했는데 왜 그런지 모르겠어서 java 11로 바꿔서 제출하니 통과가 됐다. 최근에 java 15에서 java 8로 변경했었는데 다행히 오래 헤매지 않았다. 다음부터는 기본 언어 설정을 java 11로 할 것이다.

그리고 맞았습니다 부분에서 아래의 2개는 900, 940 ms 이고 위의 2개는 852ms, 832 ms 인데
위의 2개에서는 union 할 때마다 cnt 를 증가시켜서 cnt가 m-1 개가 될 떄 break 해줌으로써 0.1 초 정도 시간을 줄일 수 있었던 것 같다.
시간복잡도 상으로는 똑같을 것 같은데, 최소 스패닝 트리의 특징을 이용하면 조금이나마 시간을 줄일 수 있다.

6. 회고

몸이 안좋아서 정답률 높고 쉬워 보이는 문제를 클릭해서 풀었다.
좀 나으면 다시 더 어려워 보이는 문제들에 도전해 볼 예정이다.

하루에 백준 1문제 이상 푸는 것을 목표로 하고있다.
https://solved.ac/profile/anwlro0212