백준 14621번: 나만 안 되는 연애 [JAVA]

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

14621번: 나만 안되는 연애

• 풀이

크루스칼 알고리즘을 이용해 최소 신장 트리를 구하되, 간선을 선택할 때 여초와 여초, 남초와 남초가 이어진 경우는 제외한다.

• 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
	static int N, M;
	static char MW[];
	static Road roads[];
	static int parent[];
	static int ans;
	
	public static class Road{
		int u, v, d;
		Road(int u, int v, int d){
			this.u = u;
			this.v = v;
			this.d = d;
		}
	}
	
	static int find(int x) {
		if (x == parent[x]) return x;
		return parent[x] = find(parent[x]);
	}
	
	static void union(int x, int y) {
		x = parent[x];
		y = parent[y];
		
		if (x<y) parent[y] = x;
		else parent[x] = y;
	}

	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(bf.readLine());
		
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		
		roads = new Road [M];
		
		// 부모 배열 초기화
		parent = new int[N+1];
		for (int i=1; i<N+1; i++) parent[i] = i;
		
		// 남초 여초 입력
		MW = new char[N+1];
		st = new StringTokenizer(bf.readLine());
		
		for (int i = 1; i<N+1; i++) {
			MW[i] = st.nextToken().charAt(0);
		}
		
		// 거리 정보 입력
		for (int i=0; i<M; i++) {
			st = new StringTokenizer(bf.readLine());
			int u = Integer.parseInt(st.nextToken());
			int v = Integer.parseInt(st.nextToken());
			int d = Integer.parseInt(st.nextToken());
			roads[i] = new Road(u, v, d);
		}
		
		Arrays.sort(roads, (r1, r2)->(r1.d - r2.d));
		
		int cnt = 0; // 연결된 학교의 수
		for (int i=0; i<M; i++) {
			// 같은 성별이 이어지거나 이미 이어진 학교의 경우 X
			if (MW[roads[i].u] == (MW[roads[i].v]) || find(roads[i].u)==find(roads[i].v)) continue;
			ans += roads[i].d;
			union(roads[i].u, roads[i].v);
			cnt++;
		}
		
		// 출력
		if (cnt!=N-1) { // 모든 학교가 이어지지 않는 경우
			System.out.println(-1);
			return;
		}
		System.out.println(ans);
	}

}