SWEA - 3124 최소 스패닝 트리

1. 문제 조건

내용

2. 아이디어

내용

3. 구현

(1) Prim Algorithm 사용

package D4;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.StringTokenizer;

public class SE_최소스패닝트리 {
	
	static class Node{
		int st;
		int ed;
		int num;
		
		Node(int ed, int num){
			this.ed = ed;
			this.num = num;
		}
	}
	
	static int V;
	static int E;
	static int inf = Integer.MAX_VALUE;
	static int[] dist;
	static List<Node>[] list;
	static boolean[] visited;
 	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		
		int T = Integer.parseInt(br.readLine());
		
		for(int t=1; t<=T; t++) {
			st = new StringTokenizer(br.readLine());
			V = Integer.parseInt(st.nextToken());
			E = Integer.parseInt(st.nextToken());
			list = new ArrayList[V+1];
			dist = new int[V+1];
			visited = new boolean[V+1];
			long answer = 0;
			
			for(int v=1; v<=V; v++) {
				list[v] = new ArrayList<>();
			}
			for(int e=0; e<E; e++) {
				st = new StringTokenizer(br.readLine());
				int start = Integer.parseInt(st.nextToken());
				int end = Integer.parseInt(st.nextToken());
				int num = Integer.parseInt(st.nextToken());
				list[start].add(new Node(end, num));
				list[end].add(new Node(start, num));
				
			}
			
			Arrays.fill(dist, inf);
			
			dist[0] = 0;
			PriorityQueue<Node> queue= new PriorityQueue<>(new Comparator<Node>() {

				@Override
				public int compare(Node o1, Node o2) {
					
					return o1.num - o2.num;
				}
			});
			for(int i=0; i<list[1].size(); i++) {
				queue.add(list[1].get(i));
			}
			visited[1] = true;
			for(int v=1; v<V; v++) {
				int idx = -1;
				int min = inf;
				while(true) {
					Node n = queue.poll();
					if(!visited[n.ed]) {
						idx = n.ed;
						visited[idx] = true;
						min = n.num;
						break;
					}
				}
				answer+= min;
				

				for(Node x : list[idx]) {
					if(!visited[x.ed]) queue.add(x);
				}
			
				
				
				
			}
		
			
			System.out.println("#"+t+" "+ answer);
			
			
		}

	}

}

(2) Kruskal Algorithm 사용

package D4;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Comparator;
import java.util.StringTokenizer;

public class SE_3124최소스패닝트리 {
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static StringTokenizer st;
	static int V;
	static int E;
	static int[] p;
	static int[][] edges;
	static long result;
	static int cnt;
	public static void main(String[] args) throws NumberFormatException, IOException {
		int T = Integer.parseInt(br.readLine());
		
		for(int t=1; t<=T; t++) {
			input();
			
		for(int i=1; i<=V; i++) {
			makeSet(i);
		}
		result = 0;
		cnt =0;
		Kruskal();
	
		System.out.println("#"+t+" " + result);
			
		}
		
	}
	static void input() throws IOException {
		stk();
		V = Integer.parseInt(st.nextToken());
		E = Integer.parseInt(st.nextToken());
		
		edges = new int[E][3];
		p = new int[V+1];
		
		for(int i=0; i<E; i++) {
			stk();
			edges[i][0] = Integer.parseInt(st.nextToken());
			edges[i][1] = Integer.parseInt(st.nextToken());
			edges[i][2] = Integer.parseInt(st.nextToken());
			
		}
	}
	
	static void sort() {
		Arrays.sort(edges, new Comparator<int[]>() {

			@Override
			public int compare(int[] o1, int[] o2) {
				return o1[2]-o2[2];
			}
		});
	}
	
	static void Kruskal() {
		sort();
		
		for(int i=0; i<E; i++) {
			int px = findSet(edges[i][0]);
			int py = findSet(edges[i][1]);
			
			if(px != py) {
				union(px,py);
				result+= edges[i][2];
				cnt++;
			}
			
			if(cnt == V-1) break;
		}
	}
	
	static void union(int x, int y) {
		p[y] = x;
	}
	
	static void makeSet(int i) {
			p[i] = i;
		
	}
	
	static int findSet(int x) {
		if(x!=p[x]) p[x] = findSet(p[x]);
		return p[x];
	}
	

	
	static void stk() throws IOException {
		st = new StringTokenizer(br.readLine());
	}
	
	

}