[백준/자바] 1922번: 네트워크 연결

문제

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

풀이

• 컴퓨터와 컴퓨터를 연결하려 한다. (a와 b가 연결되어 있고, b와 c가 연결되어 있다면, a와 c는 연결되어 있다.)
• 컴퓨터를 연결하는 비용이 주어졌을 때, 모든 컴퓨터를 연결하는데 필요한 최소비용 출력

전형적인 최소 신장 트리(MST) 문제입니다.

• 컴퓨터의 수(N) == 노드의 수
• 연결할 수 있는 선의 수(M) == 간선의 수

위처럼 이해하셨다면, 금방 풀어낼 수 있는 문제입니다.

	static class Edge implements Comparable<Edge> {
		int u, v, w;
		
		Edge (int u, int v, int w) {
			this.u = u;
			this.v = v;
			this.w = w;
		}
		
		@Override
		public int compareTo(Edge o) {
			return this.w - o.w; // 오름차순 정렬
		}
	}

• 우선 (시작 정점, 도착 정점, 가중치)를 관리하기 위해 Edge 클래스를 생성하였습니다.

    	edges = 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());
    		edges.add(new Edge(a, b, c));
    	}

• 입력 받을 때 이렇게 넣어 주시면 됩니다.

	private static void makeSet() {
		p = new int[n+1]; // 부모 배열
		s = new int[n+1]; // 크기 배열
		for (int i = 1; i <= n; i++) {
			p[i] = i; // 부모는 자기 자신
			s[i] = 1; // 크기는 자기 혼자 있으므로 1
		}
	}

• 유니온 파인드 연산에 필요한 부모 배열과 크기 배열을 초기화해 줍니다.

	private static int find(int x) {
		if (p[x] == x) return x; // 자기 자신이 부모라면 리턴
		return p[x] = find(p[x]); // 아니라면 부모의 부모 리턴(재귀)
	}

• 부모를 찾는 Find 메서드

	private static boolean union(int a, int b) {
		int ra = find(a), rb = find(b); // a와 b의 부모
		
		if (ra == rb) return false; // 같다면 union 연산을 안 했으므로, return false
		
        // ra의 밑으로 rb를 넣을 것인데, 그러려면 ra의 크기가 더 커야 함
        // 그래서 만약 rb의 크기가 더 큰 상황이라면 swap을 진행해 준다.
		if (s[ra] < s[rb]) {
			int tmp = ra;
			ra = rb;
			rb = tmp;
		}
		
		p[rb] = ra; // rb의 부모를 ra로 설정
		s[ra] += s[rb]; // ra의 밑으로 들어왔으니 rb의 크기만큼 증가
		return true; // 연산을 진행했으니 return true
	}

• Union 메서드

	private static int kruskal() {
		Collections.sort(edges); // 정렬 (가중치 오름차순)
		makeSet(); // 부모, 크기 배열 초기화
		
		int mstCost = 0; // 총 비용
		int usedEdges = 0; // 사용한 간선 수
		
		for (Edge e : edges) {
			if (union(e.u, e.v)) {
				mstCost += e.w;
				if (++usedEdges == n - 1) break;
			}
		}
		
		return mstCost;
	}

• 크루스칼 알고리즘을 사용하기 위해서 edges를 정렬
• 시작 정점과 도착 정점의 union 연산이 진행 되었다면, 그 가중치만큼 mstCost를 증가
• 간선의 개수가 (노드 - 1)개가 되었다면 종료 후 리턴

코드

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

public class Main {
	static class Edge implements Comparable<Edge> {
		int u, v, w;
		
		Edge (int u, int v, int w) {
			this.u = u;
			this.v = v;
			this.w = w;
		}
		
		@Override
		public int compareTo(Edge o) {
			return this.w - o.w;
		}
	}
	
	static int n, m;
	static int[] p, s;
	static List<Edge> edges;
	
	private static void makeSet() {
		p = new int[n+1];
		s = new int[n+1];
		for (int i = 1; i <= n; i++) {
			p[i] = i;
			s[i] = 1;
		}
	}
	
	private static int find(int x) {
		if (p[x] == x) return x;
		return p[x] = find(p[x]);
	}
	
	private static boolean union(int a, int b) {
		int ra = find(a), rb = find(b);
		
		if (ra == rb) return false;
		
		if (s[ra] < s[rb]) {
			int tmp = ra;
			ra = rb;
			rb = tmp;
		}
		
		p[rb] = ra;
		s[ra] += s[rb];
		return true;
	}
	
	private static int kruskal() {
		Collections.sort(edges);
		makeSet();
		
		int mstCost = 0;
		int usedEdges = 0;
		
		for (Edge e : edges) {
			if (union(e.u, e.v)) {
				mstCost += e.w;
				if (++usedEdges == n - 1) break;
			}
		}
		
		return mstCost;
	}
	
    public static void main(String[] args) throws IOException {
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	n = Integer.parseInt(br.readLine());
    	m = Integer.parseInt(br.readLine());
    	
    	edges = 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());
    		edges.add(new Edge(a, b, c));
    	}
    	
    	System.out.println(kruskal());
    }
}