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

문제

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

14621번: 나만 안되는 연애

풀이

Kruskal로 MST를 구한다.

단, M인 노드, W인 노드끼리만 연결할 수 있다. -> 각 노드가 어떤 성별인지 sex배열에 저장

isDiffSex()조건을 추가하여 성별이 다를 때만 edge를 선정

만약 모든 학교를 연결하는 경로가 없을 경우 -1 출력 -> edge를 연결할 때마다 count++
모든 노드가 연결된 MST는 (노드 수-1)인 경우에 해당하므로 count != V-1 이면 -1 출력

코드

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

public class Main {
    static int[] parent;
    static String[] sex;
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;

        //노드 수, 엣지 수
        st = new StringTokenizer(br.readLine());
        int V = Integer.parseInt(st.nextToken());
        int E = Integer.parseInt(st.nextToken());

        //부모 노드 초기화
        parent = new int[V+1];
        for(int i=1; i<V+1; i++)
            parent[i] = i;

        sex = new String[V+1];
        List<Edge> edgeList = new ArrayList<>();
        long sum = 0;
        int count = 0;

        //sex 배열에 노드 번호, 성별 저장
        st = new StringTokenizer(br.readLine());
        for(int i=1; i<V+1; i++){
            sex[i] = st.nextToken();
        }

        //edgeList에 양쪽 노드, 가중치 저장
        for(int i=0; i<E; i++){
            st = new StringTokenizer(br.readLine());
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());
            int weigh = Integer.parseInt(st.nextToken());
            edgeList.add(new Edge(x, y, weight));
        }

        //가중치 기준 정렬
        Collections.sort(edgeList);

        for(int i=0; i<edgeList.size(); i++){
            Edge edge = edgeList.get(i);
            if(isDiffSex(edge.x, edge.y)){
                if(!isSameParent(edge.x, edge.y)){
                    union(edge.x, edge.y);
                    sum += edge.weight;
                    count++;
                }
            }
        }

        if(count != V-1)
            sum = -1;

        bw.write(sum +" ");
        bw.close();
    }
    static boolean isDiffSex(int x, int y){
        if(!sex[x].equals(sex[y]))
            return true;
        return false;
    }
    static boolean isSameParent(int x, int y){
        x = find(x);
        y = find(y);
        if(x != y)
            return false;
        return true;
    }
    static int find(int x){
        if(parent[x] == x)
            return x;
        return parent[x] = find(parent[x]);
    }
    static void union(int x, int y){
        x = find(x);
        y = find(y);
        if(x != y)
            parent[x] = y;
    }
}

class Edge implements Comparable<Edge> {
    int x, y, weight;

    Edge(int x, int y, int weight){
        this.x = x;
        this.y = y;
        this.weigh = weight;
    }

    public int compareTo(Edge e){
        return this.weight - e.weight;
    }
}