백준_최소 스패닝 트리_1197

Kruskal은 간선리스트, Prim은 정점리스트를 사용한다.

 

Kruskal 알고리즘

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collection;
import java.util.Collections;
import java.util.StringTokenizer;

public class 최소스패닝트리_1197_kruskal {
	static int V, E, parents[];

	static class Point implements Comparable<Point> {
		int from, to, cnt;

		public Point(int from, int to, int cnt) {
			super();
			this.from = from;
			this.to = to;
			this.cnt = cnt;
		}

		@Override
		public int compareTo(Point o) {
			return Integer.compare(this.cnt, o.cnt);
		}

	}

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

		V = Integer.parseInt(st.nextToken());
		E = Integer.parseInt(st.nextToken());
		ArrayList<Point> list = new ArrayList<Point>();

		parents = new int[V + 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 cnt = Integer.parseInt(st.nextToken());
			list.add(new Point(from, to, cnt));
		}

		makeSet();
		Collections.sort(list);
		int Ans = 0;
		int v = 0;
		for (Point point : list) {
			if (v == V - 1)
				break;
			if (Union(point.from, point.to)) {
				Ans += point.cnt;
				v++;
			}
		}

		System.out.println(Ans);

	}

	private static boolean Union(int x, int y) {
		int xx = find(x);
		int yy = find(y);

		if (xx == yy)
			return false;
		parents[yy] = xx;
		return true;

	}

	private static void makeSet() {
		for (int i = 0; i < parents.length; i++) {
			parents[i] = i;
		}
	}

	private static int find(int x) {
		if (x == parents[x]) {
			return x;
		}
		return parents[x] = find(parents[x]);
	}

}

 

Prim 알고리즘

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

public class 최소스패닝트리_1197_prim {
	static int V, E;

	static class Point {
		int to, cnt;

		public Point(int to, int cnt) {
			super();
			this.to = to;
			this.cnt = cnt;
		}

	}

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

		V = Integer.parseInt(st.nextToken());
		E = Integer.parseInt(st.nextToken());
		ArrayList<Point>[] list = new ArrayList[V + 1];

		for (int i = 0; i < list.length; i++) {
			list[i] = new ArrayList<Point>();
		}

		// 인접 리스트 만들기
		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 cnt = Integer.parseInt(st.nextToken());
			list[from].add(new Point(to, cnt));
			list[to].add(new Point(from, cnt));
		}

		boolean[] v = new boolean[V + 1]; // 방문 체크
		int[] dist = new int[V + 1]; // 결과 값 저장할 배열
		Arrays.fill(dist, Integer.MAX_VALUE); // 작은 값을 저장하기 위해서 최대값으로 초기화

		dist[1] = 0; // 시작위치

		for (int i = 0; i < V - 1; i++) {
			int minIdx = 0;
			int minCnt = Integer.MAX_VALUE;

			// 값이 가장 작은 정점 구하기
			for (int j = 1; j < list.length; j++) {
				if (dist[j] < minCnt && !v[j]) {
					minIdx = j;
					minCnt = dist[j];
				}
			}

			v[minIdx] = true;
			int size = list[minIdx].size();

			for (int j = 0; j < size; j++) {
				if (!v[list[minIdx].get(j).to] && list[minIdx].get(j).cnt < dist[list[minIdx].get(j).to]) {
					dist[list[minIdx].get(j).to] = list[minIdx].get(j).cnt;
				}

			}

		}
		int Ans = 0;
		for (int i = 1; i < dist.length; i++) {
			Ans += dist[i];
		}

		System.out.println(Ans);
	}

}

 

PrioPriorityQueue 를 이용한 Prim 알고리즘

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

public class 최소스패닝트리_1197_primPQ {
	static int V, E;

	static class Point implements Comparable<Point> {
		int to, cnt;

		public Point(int to, int cnt) {
			super();
			this.to = to;
			this.cnt = cnt;
		}

		@Override
		public int compareTo(Point o) {
			// TODO Auto-generated method stub
			return Integer.compare(this.cnt, o.cnt);
		}

	}

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

		V = Integer.parseInt(st.nextToken());
		E = Integer.parseInt(st.nextToken());
		ArrayList<Point>[] list = new ArrayList[V + 1];

		for (int i = 0; i < list.length; i++) {
			list[i] = new ArrayList<Point>();
		}

		// 인접 리스트 만들기
		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 cnt = Integer.parseInt(st.nextToken());
			list[from].add(new Point(to, cnt));
			list[to].add(new Point(from, cnt));
		}

		boolean[] v = new boolean[V + 1]; // 방문 체크
		int[] dist = new int[V + 1]; // 결과 값 저장할 배열
		PriorityQueue<Point> PQ = new PriorityQueue<Point>();
		Arrays.fill(dist, Integer.MAX_VALUE); // 작은 값을 저장하기 위해서 최대값으로 초기화

		dist[1] = 0; // 시작위치

		PQ.add(new Point(1, dist[1]));
		Point current = null;
		while (!PQ.isEmpty()) {

			// 값이 가장 작은 정점 구하기
			current = PQ.poll();

			v[current.to] = true;
			int size = list[current.to].size();

			for (int j = 0; j < size; j++) {
				if (!v[list[current.to].get(j).to] && list[current.to].get(j).cnt < dist[list[current.to].get(j).to]) {
					dist[list[current.to].get(j).to] = list[current.to].get(j).cnt;
					PQ.add(new Point(list[current.to].get(j).to, dist[list[current.to].get(j).to]));
				}

			}

		}
		int Ans = 0;
		for (int i = 1; i < dist.length; i++) {
			Ans += dist[i];
		}
//		System.out.println(Arrays.toString(dist));

		System.out.println(Ans);
	}

}