백준 14621 : 나만 안되는 연애

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

14621번: 나만 안되는 연애

[ 문제풀이 ]

결국 모든 정점을 구성하는 최소 신장 트리를 만드는 것이기 때문에 크루스칼이나 프림 알고리즘을 활용하면 쉽게 해결할 수 있다.

3가지 특징 중 2, 3번 특징은 MST를 의미하며 1번 특징만 고려해서 같은 성별의 대학교만 연결 못되도록 간선을 처리해주면 된다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.HashMap;
import java.util.Map;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {

	static class Edge implements Comparable<Edge> {
		int from, to, cost;
		
		public Edge(int from, int to, int cost) {
			this.from = from;
			this.to = to;
			this.cost = cost;
		}

		@Override
		public int compareTo(Edge o) {
			return this.cost - o.cost;
		}
	}
	
	static int N, M;
	static int[] parent;
	static Map<Integer, Integer> hm;
	static Queue<Edge> pq;
	
	public static void main(String[] args) throws IOException {
		try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
				BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out))) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			N = Integer.parseInt(st.nextToken());
			M = Integer.parseInt(st.nextToken());
			hm = new HashMap<>();
			parent = new int[N + 1];
			st = new StringTokenizer(br.readLine());
			for (int i = 1; i <= N; ++i) {
				if (st.nextToken().equals("M")) {
					hm.put(i, 1);
				} else {
					hm.put(i, 0);
				}
				parent[i] = i;
			}

			pq = new PriorityQueue<>();
			for (int i = 0; i < M; ++i) {
				st = new StringTokenizer(br.readLine());
				int u = Integer.parseInt(st.nextToken());
				int v = Integer.parseInt(st.nextToken());
				int cost = Integer.parseInt(st.nextToken());
				pq.offer(new Edge(u, v, cost));
			}
		
			int connect = 1, ans = 0;
			while (!pq.isEmpty() && connect <= N) {
				Edge e = pq.poll();
				
				if (isConnect(e.from, e.to)) continue;
				
				union(e.from, e.to);
				connect++;
				ans += e.cost;
			}
			if (connect == N) bw.write(ans + "\n");
			else bw.write(-1 + "\n");
		} catch (Exception e) {
			e.printStackTrace();
		}
	}
	
	public static boolean isConnect(int u, int v) {
		if ((hm.get(u) + hm.get(v)) % 2 == 0) return true;
		return getParent(u) == getParent(v);
	}
	
	public static int getParent(int v) {
		return v == parent[v] ? v : (parent[v] = getParent(parent[v]));
	}
	
	public static void union(int u, int v) {
		parent[getParent(v)] = getParent(u);
	}
}