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

14621번: 나만 안되는 연애

---

[최소 스패닝 트리(Minimum Spanning Tree, MST), 크루스칼]

남초와 여초만을 이어주는 경로만 존재한다고 생각하면 쉽다. 문제에서 2번째 줄에 M W W W M 이런 식으로 주어지는데, 이를 boolean[ ]에 저장을 한다. 예를 들어 1번 째 학교가 M(남초) 이면 true, 2번 째 학교가 W(여초)이면 false 이런 식으로.

 

그럼 간선 정보가 주어질 때 선별적으로 간선을 저장할 수 있다.

        for(int i=0; i<m; i++) {
            st = new StringTokenizer(br.readLine());

            int h = Integer.parseInt(st.nextToken());
            int t = Integer.parseInt(st.nextToken());
            int d = Integer.parseInt(st.nextToken());

            if (univ[h] != univ[t])
                list.add(new Edge(h, t, d));
        }

여기까지 성공했다면 나머지는 일반적인 크루스칼 알고리즘을 이용하면 쉽게 마무리 지을 수 있다.

# Code </>

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {

    static class Edge{
        int h, tg, d;
        
        public Edge(int home, int target, int dist){
            h=home;
            tg=target;
            d=dist;
        }
    }

    static List<Edge> list = new ArrayList<>();
    static boolean[] univ = new boolean[1001];
    static int[] parent = new int[1001];

    static int getParent(int x){
        if(parent[x] == x) return x;
        return parent[x] = getParent(parent[x]);
    }
    static boolean findParent(int a, int b){
        a = getParent(a);
        b = getParent(b);

        return a == b;
    }
    static void union(int a, int b){
        a = getParent(a);
        b = getParent(b);

        if(b < a)
            parent[a] = b;
        else
            parent[b] = a;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());

        st = new StringTokenizer(br.readLine());
        for(int i=1; i<=n; i++) {
            univ[i] = st.nextToken().equals("M");
            parent[i] = i;
        }

        for(int i=0; i<m; i++) {
            st = new StringTokenizer(br.readLine());

            int h = Integer.parseInt(st.nextToken());
            int t = Integer.parseInt(st.nextToken());
            int d = Integer.parseInt(st.nextToken());

            if (univ[h] != univ[t])
                list.add(new Edge(h, t, d));
        }

        Collections.sort(list, (a, b) -> a.d - b.d);

        int sum = 0;
        
        for(Edge e : list)
            if(!findParent(e.h, e.tg)){
                sum += e.d;
                union(e.h, e.tg);
            }

        boolean flag = true;
        
        for(int i=1; i<=n; i++)
            if(parent[1] != getParent(parent[i])) {
                flag = false;
                break;
            }

        System.out.println(flag? sum : -1);
    }
}