[JAVA] 백준 1197번 - 최소 스패닝 트리

1197번: 최소 스패닝 트리 (acmicpc.net)

1197번: 최소 스패닝 트리

스패닝 트리 구현법!

MST가 최소비용신장트리를 말하는데 간선들의 가중치 합이 최소인 신장 트리를 말한다네용 그 방법에는 

1. 크루스칼 -> 유니온 파인드 사용 

2. 프림 -> 우선순위큐로 다익스트라 하듯이 

하면 된다는데

유니온 파인드 며칠 전에 해봤으니 응용삼아 크루스칼로 해보겠슴니다

 

할 때 중요한게 간선 중심으로 오름차순으로 정리해야한대요

이때 정렬 위해서 Comparable<T> 인터페이스를 사용하는데 첨 봐서 찾아봤슴니다

코딩의 시작, TCP School

코딩교육 티씨피스쿨

package baekjoon;
import java.util.*;
import java.io.*;

class edge implements Comparable<edge>
{
	int start;
	int end;
	int cost;
	
	public edge(int start, int end, int cost)
	{
		this.start = start;
		this.end = end;
		this.cost = cost;
	}
	
	@Override
	public int compareTo(edge obj)
	{
		return obj.cost >= this.cost ? -1 : 1;
	}
}
public class b1197 {
	static ArrayList <edge> list;
	static int[] parent;
	public static void main(String[] args) throws IOException{
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		int V = Integer.parseInt(st.nextToken());
		int E = Integer.parseInt(st.nextToken());
		parent = new int [V+1];
		
		for(int i = 1 ; i <= V ; i++)
			parent[i] = i;
		
		list = new ArrayList<edge>(); // ArrayList 초기화
		for(int i = 0 ; i < E ; i++)
		{
			st = new StringTokenizer(br.readLine());
			list.add(new edge(Integer.parseInt(st.nextToken()),Integer.parseInt(st.nextToken()),Integer.parseInt(st.nextToken())));
		}
		Collections.sort(list);
		
		int sum = 0;
		for(edge i : list)
		{
			if(union(i.start, i.end))
				sum += i.cost;
		}
		bw.write(sum+"");
		bw.close();
	}
	public static int find(int n)
	{
		if(parent[n] == n)
			return n;
		return parent[n] = find(parent[n]);
	}
	public static boolean union(int n, int m)
	{
		int nRoot = find(n);
		int mRoot = find(m);
		
		if(nRoot != mRoot)
		{
			parent[mRoot] = nRoot;
			return true;
		}
		else
			return false;
	}
}

유니온 파인드 외워야겠어요..

 

알리에서 산 버티컬 마우스 후기인데요..

이거 풀면서 구글링하고 코드 드래그하고 하면서 느낀 점인데요...

돈 더 주고 비싼거 사야겠다 싶었슴니다...커서가 드 르르 르 르륵 움직임 ㅠ