[BAEKJOON_1197 - JAVA] 최소 스패닝 트리(MST)

문제

www.acmicpc.net/problem/1197

1197번: 최소 스패닝 트리

 

 

풀이

• 최소 스패닝 트리 기본 문제, 개념을 다시 상기 시키고자 풀이. ( 꾸준히 해야 까먹지 않는다.)
• Prim과 Kruscal 모두 시도.
• 간적크 간많프 →  간선이 적으면 크루스칼 알고리즘 / 간선이 많으면 프림 알고리즘
  ex) 항상 위와 같지는 않다. 하지만 대부분 간선의 갯수에 따라 알고리즘을 선택
• MST를 한다면 프림과 크루스칼 두가지 방법으로 풀어보는 것을 추천.
• 프림의 경우 visit을 통한 방문관리로 사이클의 걱정이 없지만, 크루스칼의 경우 union을 하기 전에 반드시 사이클이 생기는지를 확인 해야한다.( 밑의 크루스칼 풀이 코드에 find()함수를 통한 a==b 같은 경우가 이에 해당된다.)

 

 

과정

1. Kruscal
   1. 오름차순으로 정렬 ( 필자가 푼 코드는 priorityQueue 를 사용해 오름차순으로 정렬)
   2. make()
      상위 노드를 초기화 하는 함수.
   3. find()
      부모 노드를 찾는 함수.
   4. union()
      최상위 노드를 합치는 함수. → 사이클이 생기지 않게 조심
2. Prim
   1. 인접 행렬 생성.
   2. 우선순위 큐에 시작정점 1을 담아 시작.
   3. 연결된 정점의 모든 간선들 중 방문하지 않은 Node 탐색, pq에 삽입.
   4. 모든 노드를 방문 할때까지 반복.

 

 

알고리즘 지식

• MST(Kruscal or Prim)

2020/03/11 - [JAVA/JAVA - 알고리즘 개념] - [MST 개념] 최소 비용 신장 트리

[MST 개념] 최소 비용 신장 트리

 

 

JAVA코드

1. Kruscal 알고리즘 풀이

 package BaekJoon_2020_12_23__30;

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

/**
 * Kruscal 알고리즘 풀이
 * @packageName : BaekJoon_2020_12_23__30
 * @fileName : BJ_1197_최소스패닝트리.java
 * @author : Mingeon
 * @date : 2020. 12. 24.
 * @language : JAVA
 * @classification :
 * @time_limit :
 * @required_time :
 * @submissions :
 * @description
 */

public class BJ_1197_최소스패닝트리_Kruscal {

	static int V; // 정점의 갯수
	static int E; // 간선의 갯수
	static int[] parent;
	static PriorityQueue<Edge> pq = new PriorityQueue<Edge>();

	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()); // 간선의 갯수

		make();

		for (int i = 0; i < E; i++) {
			st = new StringTokenizer(br.readLine());
			pq.add(new Edge(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()),
					Integer.parseInt(st.nextToken())));
		} // End of input

		System.out.println(Kruscal());
	}

	private static int Kruscal() {
		int ret = 0;
		int cnt = 0;

		while (!pq.isEmpty()) {
			Edge temp = pq.poll();

			int a = find(temp.start);
			int b = find(temp.end);

			// 사이클이 생기므로 continue.
			if (a == b) {
				continue;
			}

			union(a, b);
			ret += temp.value;
			if (++cnt == V) {
				break;
			}
		}

		return ret;
	}

	// 상위 노드 초기화
	private static void make() {
		parent = new int[V + 1];
		for (int i = 1; i < V + 1; i++) {
			parent[i] = i;
		}
	}

	// union find
	private static int find(int a) {
		if (a == parent[a]) {
			return a;
		}
		return parent[a] = find(parent[a]);
	}

	private static void union(int a, int b) {

		// 최상위 노드 탐색
		int aRoot = find(a);
		int bRoot = find(b);

		// 최상위 노드가 같지 않은 경우
		if (aRoot != bRoot) {
			parent[aRoot] = bRoot;
		} else {
			return;
		}
	}

}

class Edge implements Comparable<Edge> {
	int start;
	int end;
	int value;

	public Edge(int start, int end, int value) {
		this.start = start;
		this.end = end;
		this.value = value;
	}

	@Override
	public int compareTo(Edge o) {
		return o.value >= this.value ? -1 : 1;
	}

}

 

 

2. Prim 알고리즘 풀이

package BaekJoon_2020_12_23__30;

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

/**
 * Prim 알고리즘 풀이
 * @packageName : BaekJoon_2020_12_23__30
 * @fileName : BJ_1197_최소스패닝트리.java
 * @author : Mingeon
 * @date : 2020. 12. 24.
 * @language : JAVA
 * @classification : MST
 * @time_limit : 2sec
 * @required_time :
 * @submissions : 1
 * @description
 */

public class BJ_1197_최소스패닝트리_Prim {

	static int V; // 정점의 갯수
	static int E; // 간선의 갯수
	static boolean[] visited; // 방문 관리
	static ArrayList<Node>[] adj; // 인접 리스트
	static PriorityQueue<Node> pq; // 우선순위 큐

	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()); // 간선의 갯수

		// 인접 리스트 생성
		adj = new ArrayList[V + 1];
		for (int i = 1; i <= V; i++) {
			adj[i] = new ArrayList<>();
		}

		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());

			// 인접 리스트
			adj[from].add(new Node(to, value));
			adj[to].add(new Node(from, value));
		} // End of input

		System.out.println(prim());
	}

	private static int prim() {
		int ret = 0;
		visited = new boolean[V + 1]; // 방문 관리
		pq = new PriorityQueue<Node>(); // 우선 순위 큐
		pq.add(new Node(1, 0));

		int cnt = 0;
		while (!pq.isEmpty()) {

			Node edge = pq.poll();

			// 이미 방문한 정점인 경우
			if (visited[edge.to]) {
				continue;
			}

			ret += edge.value;
			visited[edge.to] = true;

			// 모든 노드를 방문한 경우
			if (++cnt == V) {
				return ret;
			}

			// 연결된 노드들 중 방문하지 않은 노드 탐색
			for (int i = 0; i < adj[edge.to].size(); i++) {
				Node next = adj[edge.to].get(i);
				if (visited[next.to]) {
					continue;
				}

				pq.add(next);
			}

		}

		return ret;
	}

}

class Node implements Comparable<Node> {
	int to;
	int value;

	public Node(int to, int value) {
		this.to = to;
		this.value = value;
	}

	@Override
	public int compareTo(Node o) {
		return o.value >= this.value ? -1 : 1;
	}

}