[백준 1992] 네트워크 연결(java)-최소 스패닝 트리(MST)

최소 스패닝 트리 2가지 알고리즘 내용

 

문제 보러 가기

1922번: 네트워크 연결

이 문제는 최소 스패닝 트리의 가장 기본적인 구현을 다루는 문제이다. 최소 스패닝 트리는 스패닝 트리 중(그래프 내의 모든 정점을 포함하는 트리) 연결된 간선 가중치가 가장 작은 것들로 구성된 트리를 의미한다.

 

모든 정점을 포함하기 위해서는 하나의 트리로 연결돼야 하는데 이때 사용하는 알고리즘이 크루스칼, 프림 2가지의 방법이 있다. 이 중 크루스칼을 이용하여 풀이하였다.

 

 

 

 

 

 

 

문제풀이

크루스칼 알고리즘은 Union-Find를 사용하여 구현할 수 있다. -> Union-Find 설명

 

- 간선의 정보를 list에 저장한다.

- 최소 가중치의 트리를 만들기 위해 간선 list를 오름차순으로 정렬한다.

- 정렬된 간선 list에서 노드를 하나씩 연결하기 위해 union-find를 이용한다.

- 이미 연결된 노드일 경우 넘어가고, 새로 연결될 경우 가중치를 총비용에 더한다.

 

 

 

 

 

 

 

public class Ex_1922 {

	static int[] root;
	static List<Edge> list;

	public static void main(String[] args) throws Exception {
		// TODO Auto-generated method stub
		// 최소 스패닝 트리/네트워크 연결
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		int m = Integer.parseInt(br.readLine());
		root = new int[n + 1];
		list = new ArrayList<>();

		for (int i = 0; i < m; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			int c = Integer.parseInt(st.nextToken());
			list.add(new Edge(a, b, c));

		}
		for (int i = 0; i <= n; i++)
			root[i] = i;
		
		Collections.sort(list);
		
		long result = 0;
		for (Edge e : list) {
			int start = e.a;
			int end = e.b;
			int res = find(start, end);
			
			if (res == 1) 
				continue;
			
			union(start, end);
			result += e.c;
		}
		System.out.println(result);

	}

	static int parent(int idx) {
		if (root[idx] == idx)
			return idx;
		return root[idx] = parent(root[idx]);
	}

	static void union(int a, int b) {
		a = parent(a);
		b = parent(b);
		if (a < b)
			root[b] = a;
		else
			root[a] = b;
	}

	static int find(int a, int b) {
		a = parent(a);
		b = parent(b);
		if (a == b)
			return 1;
		else
			return 0;
	}

	static class Edge implements Comparable<Edge> {
		int a;
		int b;
		int c;

		Edge(int a, int b, int c) {
			this.a = a;
			this.b = b;
			this.c = c;
		}

		@Override
		public int compareTo(Edge e) {
			return c - e.c;
		}
	}

}