[백준] 14621: 나만 안되는 연애 - 최소신장트리(Minimum Spanning Tree, MST) + 크루스칼(Kruskal) JAVA

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

14621번: 나만 안되는 연애

코드설명

최소신장트리(Minimum Spanning Tree, MST) + 크루스칼(Kruskal) 문제에 약간의 로직이 추가되었습니다.

 

1. Node의 상태에 따라서 UnionParent를 할지말지 결정합니다.

-  학교가 남초대학교(M)인지, 여초대학교(W)인지를 Node에 저장해서 가지고 있다가

    만약 서로 연결된 관계가 M-W 일 경우에만 unionParent를 해주는 로직을 수행하면 됩니다.

 

2. 최소 신장 트리의 연결된 간선의 개수는 무조건 N - 1 입니다.

코드

package algorhythm;

import java.util.*;

public class Main {
	public static int[] parent = new int[1001];
	public static ArrayList<Node> nodes = new ArrayList<>();
	public static ArrayList<Edge> edges = new ArrayList<>();
	public static int N, M, result=0, cnt = 0;
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		N = sc.nextInt();
		M = sc.nextInt();
		
		for(int i=1;i<=N;i++) {
			parent[i] = i;
		}
		
		for(int i=0;i<N;i++) {
			char gender = sc.next().charAt(0);
			nodes.add(new Node(gender));
//			System.out.println("gender"+ gender);
		}
		
		for(int i=0;i<M;i++) {
			int a = sc.nextInt();
			int b = sc.nextInt();
			int cost = sc.nextInt();
			edges.add(new Edge(a, b, cost));
		}
		
		Collections.sort(edges);
		
		for(int i=0;i<edges.size();i++) {
			int a = edges.get(i).nodeA;
			int b = edges.get(i).nodeB;
			int cost = edges.get(i).distance;
			if(findParent(a) != findParent(b)) {
				if( nodes.get(a-1).gender != nodes.get(b-1).gender ) {
					unionParent(a, b);
					result += cost;
                    cnt+=1;
				}
			}
		}
		if(cnt == N-1) 
		System.out.println(result);
        else 
        System.out.println("-1");
	
	}
	
	public static int findParent(int x) {
		if( x == parent[x]) return x;
		return parent[x] = findParent(parent[x]);
	}
	
	public static void unionParent(int a, int b) {
		a = findParent(a);
		b = findParent(b);
		if( a < b ) parent[b] = a;
		else parent[a] = b;
	}
	
	
	
}

class Node{
	char gender;
	public Node(char gender) {
		this.gender = gender;
	}
}


class Edge implements Comparable<Edge>{
	int nodeA;
	int nodeB;
	int distance;
	
	public Edge(int nodeA, int nodeB, int distance) {
		this.nodeA = nodeA;
		this.nodeB = nodeB;
		this.distance = distance;
	}
	
	//거리가 짧은 순으로 정렬하도록 합니다.
	@Override
	public int compareTo(Edge other) {
		if(this.distance > other.distance) {
			return 1;
		}else if(this.distance < other.distance) {
			return -1;
		}else {
			return 0;
		}
	}
}