[BOJ 1197] 최소 스패닝 트리

문제

• BOJ 1197
• 문제의 저작권은 Baekjoon Online Judge에 있습니다.

접근방식

MST의 대표적인 문제로 암기될 때까지 반복해서 공부하면 좋다!
1. 프림알고리즘</br>
연결된 정점의 정보를 저장하는 연결리스트와 우선순위큐를 사용해 구현하였다.
임의의 정점에서 시작해서 인접한 간선정보를 리스트에서 가져와 우선순위큐에 모두 넣고, 우선순위큐로 부터 가중치가 가장 작은 정점을 꺼내서 다음 방문할 정점으로 정하고 이를 반복한다.
한번 방문한 정점을 다시 방문하면 사이클이 발생하므로 이는 트리의 성질에 어긋난다. 이를 방지하기 위해서 visit[V]배열로 방문 여부를 관리한다.

2. 크루스칼 알고리즘</br> 서로소집합 연산을 활용해서 각 노드를 독립적인 집합으로 두고(make) 간선리스트에 저장된 두 정점(from, to)를 하나씩 꺼내서 union연산으로 하나의 집합으로 합칠지 말지를 결정한다. 이 때, find()로 각 노드의 대표노드를 찾아와서 서로 다를경우 합친다. 합치기 위해서 오른쪽의 대표노드(루트노드)의 부모를 왼쪽의 루트노드로 바꿔주면 된다. 그리고 추가로 부모를 찾아갈때 거쳐거나는 간선을 줄이기 위해서 find()에서 패스압축을 시키기 위해 루트노드를 다이렉트로 자기 자신의 부모로 가지도록 설정했다.

코드

1. 프림 알고리즘
   ```java import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.PriorityQueue; import java.util.StringTokenizer;

//프림알고리즘 public class Main {

static int V, E;
static int from, to;
static long weight;
static ArrayList<Node>[] graph; //간선 정보
static int Ans; //최소신장트리의 가중치
static StringTokenizer st;

public static void main(String[] args) throws NumberFormatException, IOException {
	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	st = new StringTokenizer(br.readLine());
	V = Integer.parseInt(st.nextToken());
	E = Integer.parseInt(st.nextToken());
	
	graph = new ArrayList[V + 1]; //1번~V번
	
	for(int i=1; i<V+1; i++) {
		graph[i] = new ArrayList<>();
	}
	
	for(int i=0; i<E; i++) {
		st = new StringTokenizer(br.readLine());
		from = Integer.parseInt(st.nextToken());
		to = Integer.parseInt(st.nextToken());
		weight = Long.parseLong(st.nextToken());
		graph[from].add(new Node(to, weight));
		graph[to].add(new Node(from, weight));
	}
	
	makeMST();
	System.out.println(Ans);
}


//최소 신장 트리
private static void makeMST() {
	PriorityQueue<Node> pq = new PriorityQueue<>();
	boolean[] visited = new boolean[V+1];
	int now = 1; //1번 정점에서 출발
	visited[1] = true; //방문 표시
	
	//모든 정점 돌아야하니까
	for(int i=1; i<V; i++) {
		 //현재 정점에 있는 간선 정보를 큐에다 넣어줌
		for(Node node : graph[now]) {
			if(!visited[node.num])  //아직 방문하지 않았다면
				pq.offer(node);
			
		}
		//다음으로 갈 정점 찾기
		//큐에 담긴 정점 중 가장 가중치가 작은 정점 고르기
		while(!pq.isEmpty()) {
			Node node = pq.poll();
			if(!visited[node.num]) {
				now = node.num;
				visited[now] = true;
				Ans += node.weight;
				break;
			}
		}
	}
}

static public class Node implements Comparable<Node>{
	int num; //연결된 정점
	long weight; //가중치
	
	public Node(int num, long weight) {
		super();
		this.num = num;
		this.weight = weight;
	}

	@Override
	public int compareTo(Node o) {
		// TODO Auto-generated method stub
		return Long.compare(this.weight, o.weight);
	}
} } ```