[SWEA JAVA] 3124. 최소 스패닝 트리

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV_mSnmKUckDFAWb

SW Expert Academy

 

1. 크루스칼 풀이

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

public class Solution {
	public static int T, V, E, cnt = 0;
	public static long Min = 0;
	public static int[] p, size;
	public static List<Line> list;

	public static class Line {
		int from, to, value;

		public Line(int from, int to, int value) {
			super();
			this.from = from;
			this.to = to;
			this.value = value;
		}

	}

	public static void make() {
		for (int i = 1; i < V + 1; i++) {
			p[i] = i;
		}
	}

	public static boolean Union(int a, int b) {
		int aRoot = findSet(a);
		int bRoot = findSet(b);
		if (aRoot == bRoot)
			return false;
		if (size[aRoot] > size[bRoot])
			p[bRoot] = aRoot;
		else if (size[aRoot] == size[bRoot])
			size[bRoot]++;

		if (size[bRoot] > size[aRoot]) {
			p[aRoot] = bRoot;
		}
		return true;
	}

	public static int findSet(int a) {
		if (a == p[a])
			return a;
		p[a] = findSet(p[a]);
		return p[a];
	}

	public static int check(int a, int b) {
		int aRoot = findSet(a);
		int bRoot = findSet(b);
		if (aRoot == bRoot)
			return 1;
		else
			return 0;
	}

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;

		T = Integer.parseInt(br.readLine());
		for (int tc = 1; tc <= T; tc++) {

			st = new StringTokenizer(br.readLine());

			V = Integer.parseInt(st.nextToken());
			E = Integer.parseInt(st.nextToken());

			p = new int[V + 1];
			size = new int[V + 1];
			list = new ArrayList<>();
			make();

			for (int i = 0; i < E; i++) {
				st = new StringTokenizer(br.readLine());
				int from = Integer.parseInt(st.nextToken());
				int to = Integer.parseInt(st.nextToken());
				int value = Integer.parseInt(st.nextToken());
				list.add(new Line(from, to, value));
			}

			list.sort((o1, o2) -> Integer.compare(o1.value, o2.value));
			
			cnt = 0;
			Min = 0;
			
			for (int i = 0; i < E; i++) {

				Line cur = list.get(i);
				if (Union(cur.from, cur.to)) { // Union가능하다면
					cnt++;
					Min += cur.value;
				}

				if (cnt == V - 1)
					break;
			}

			System.out.println("#" + tc + " " + Min);
		}

	}
}

 

2. 프림 알고리즘

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

public class Main {
	public static int T, V, E, cnt = 0;
	public static long ans = 0;
	public static boolean[] visited;
	public static List<Edge>[] list; 

	public static class Edge implements Comparable<Edge> {
		int w;
		int cost;

		public Edge(int w, int cost) {
			super();
			this.w = w;
			this.cost = cost;
		}

		@Override
		public int compareTo(Edge o) {
			return this.cost - o.cost;
		}
	}

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		T = Integer.parseInt(br.readLine());

		for (int tc = 1; tc <= T; tc++) {
			st = new StringTokenizer(br.readLine());
			V = Integer.parseInt(st.nextToken()); // 정점 수
			E = Integer.parseInt(st.nextToken()); // 간선 수

			list = new ArrayList[V + 1];
			for(int i =1;i<=V;i++) {
				list[i] = new ArrayList<>();
			}
			visited = new boolean[V + 1]; // 방문여부 배열 (트리 포함정점배열)
			
			// 1-1. 간선 입력받기
			for (int i = 0; i < E; i++) {
				st = new StringTokenizer(br.readLine());
				int from = Integer.parseInt(st.nextToken());
				int to = Integer.parseInt(st.nextToken());
				int value = Integer.parseInt(st.nextToken());
				list[from].add(new Edge(to, value));
				list[to].add(new Edge(from, value));
			}

			// 3. 프림
			ans = 0;
			cnt = 0;

			PriorityQueue<Edge> q = new PriorityQueue<>(); // 자신과 타정점들간의 간선비용 중 최소 간선 비용
			q.offer(new Edge(1, 0));// 0번 정점을 트리의 시작 정점이 되도록 함 (다른 정점이어도 상관없음)
			
			while (!q.isEmpty()) {
				// step1 : 트리 구성에 포함된 가장 유리한 정점 선택( 비트리 정점 중 최소비용 간선의 정점 선택 )
				Edge edge = q.poll();
				int v = edge.w;
				int cost = edge.cost;
				
				if (visited[v])
					continue;

				visited[v] = true;
				ans += cost;
				
				if(++cnt == V) break;

				// step2 : 선택된 정점과 타 정점들 간선비용 비교하기
				for (Edge d: list[v]) {
					if (!visited[d.w]) {
						q.offer(d);
					}
				}
			}

			// 4. 출력
			System.out.println("#" + tc + " " + ans);
		}

	}
}

 

 

 

 

출력 자료형에 주의