백준 1922 / 네트워크 연결

https://www.acmicpc.net/problem/1922

 

 

정점 위주 : 크루스칼 (유니온파인드 + pq로 노드 정렬)

import java.util.*;
import java.io.*;

public class 네트워크연결 {
	static class Node{
		int a;
		int b;
		int c;
		Node(int a, int b, int c){
			this.a = a;
			this.b = b;
			this.c = c;
		}
	}
	static int N, M, result;
	static int[] parent, rank;
	
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		PriorityQueue<Node> pq = new PriorityQueue<>((o1,o2) -> (o1.c-o2.c));
		N = Integer.parseInt(br.readLine());
		parent = new int[N+1];
		rank = new int[N+1];
		for(int i = 1; i<=N; i++) {
			parent[i] = i;
			rank[i] = 1;
		}
		M = Integer.parseInt(br.readLine());
		for(int i = 0; i < M; i++) {
			st = new StringTokenizer(br.readLine());
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			int c = Integer.parseInt(st.nextToken());
			pq.add(new Node(a,b,c));
		}
		result = 0;
		int size = pq.size();
		for(int i = 0; i < size; i++) {
			Node now = pq.poll();
			union(now.a, now.b, now.c);
		}
		System.out.println(result);
//		System.out.println(Arrays.toString(parent));
	}

	private static void union(int a, int b, int c) {
		int pa = find(a);
		int pb = find(b);
		if(find(pa)==find(pb)) return;
		if(rank[pa]<rank[pb]) {
			rank[pb]+=rank[pa];
			parent[pa] = pb;
		}else {
			rank[pa]+=rank[pb];
			parent[pb] = pa;
		}
		result += c;
	}

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

 

 

간선 위주 : 프림 (연결리스트로 정점들을 간선위주로 정렬), bfs탐색과 유사한 방법

import java.util.*;
import java.io.*;

public class 네트워크연결 {
	
	static class Edge{
		int to;
		int weight;
		Edge(int to, int weight){
			this.to = to;
			this.weight = weight;
		}
	}
	static int N, M, result;
	static int[] parent, rank;
	
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		N = Integer.parseInt(br.readLine());
		M = Integer.parseInt(br.readLine());
		ArrayList<Edge>[] list = new ArrayList[N+1];
		for(int i = 1; i <= N; i++) {
			list[i] = new ArrayList<>();
		}
		for(int i = 0; i < M; i++) {
			st = new StringTokenizer(br.readLine());
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			int c = Integer.parseInt(st.nextToken());
			
			list[a].add(new Edge(b, c));
			list[b].add(new Edge(a, c));
		}
		
		boolean[] visited = new boolean[N+1];
		PriorityQueue<Edge> pq = new PriorityQueue<>((o1,o2)->(o1.weight-o2.weight));
		
		visited[1] = true; //1번 정점부터 시작
		for(Edge e : list[1]) {
			pq.offer(e);
		}
		
		int result = 0;
		int cnt = 1; //연결된 정점의 수
		
		while(!pq.isEmpty() && cnt<N) {
			Edge curr = pq.poll();
			
			if(visited[curr.to]) continue;
			
			visited[curr.to] = true;
			result += curr.weight;
			cnt++;
			
			for(Edge next : list[curr.to]) {
				if(!visited[next.to]) {
					pq.offer(new Edge(next.to, next.weight));
				}
			}
		}
		System.out.println(result);
		
	}
}