[백준] 1922번. 네트워크 연결 (java, mst, 크루스칼)

www.acmicpc.net/problem/1922

1922번: 네트워크 연결

--- 수정 

자체 정렬 조건을 넣어줘서 priorityqueue없이 그냥 Computer배열을 만든 다음에 

Arrays.sort(list)를 해주면 된다.

 

import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.Scanner;

class Computer implements Comparable<Computer>{
	int x,y;
	int cost;
	public Computer(int x, int y, int cost) {
		super();
		this.x = x;
		this.y = y;
		this.cost = cost;
	}
	@Override
	public int compareTo(Computer o) {
		return this.cost-o.cost;
	}
	
}

public class Main {
	static int n,m;
	static int[][] map;
	static int[] parent;
	static int answer;
	static int cnt;
	static Computer[] list;
	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		n=sc.nextInt();
		m=sc.nextInt();
		parent=new int[n+1];
		for (int i = 1; i <=n; i++) {
			parent[i]=i;
		}
		list=new Computer[m];
		for (int i = 0; i < m; i++) {
			int a=sc.nextInt();
			int b=sc.nextInt();
			int cost=sc.nextInt();
			list[i]=new Computer(a,b,cost);
		}
		Arrays.sort(list);
		for(Computer cur:list) {
			union(cur.x,cur.y,cur.cost);
			if(cnt==n-1) {
				break;
			}
		}
		System.out.println(answer);
	}
	private static int find(int x) {
		if(x==parent[x])return x;
		else return parent[x]=find(parent[x]);
	}
	private static void union(int x, int y,int cost) {
		x=find(x);
		y=find(y);
		if(x!=y) {
			answer+=cost;
			cnt++;
			if(x<y) {
				parent[y]=x;
			}else {
				parent[x]=y;
			}
		}
		
	}
}

 

 

 

---

이전 코드

import java.util.PriorityQueue;
import java.util.Scanner;

class Computer implements Comparable<Computer>{
	int x,y;
	int cost;
	public Computer(int x, int y, int cost) {
		super();
		this.x = x;
		this.y = y;
		this.cost = cost;
	}
	@Override
	public int compareTo(Computer o) {
		return this.cost-o.cost;
	}
	
}

public class Main {
	static int n,m;
	static int[][] map;
	static int[] parent;
	static int answer;
	static int cnt;
	static PriorityQueue<Computer> pq=new PriorityQueue<>();
	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		n=sc.nextInt();
		m=sc.nextInt();
		parent=new int[n+1];
		for (int i = 1; i <=n; i++) {
			parent[i]=i;
		}
		for (int i = 0; i < m; i++) {
			int a=sc.nextInt();
			int b=sc.nextInt();
			int cost=sc.nextInt();
			pq.add(new Computer(a,b,cost));
		}
		int size=pq.size();
		for (int i = 0; i < size; i++) {
			Computer cur=pq.poll();
			union(cur.x,cur.y,cur.cost);
			if(cnt==n-1) {
				break;
			}
		}
		System.out.println(answer);
	}
	private static int find(int x) {
		if(x==parent[x])return x;
		else return parent[x]=find(parent[x]);
	}
	private static void union(int x, int y,int cost) {
		x=find(x);
		y=find(y);
		if(x!=y) {
			answer+=cost;
			cnt++;
			if(x<y) {
				parent[y]=x;
			}else {
				parent[x]=y;
			}
		}
		
	}
}