백준 14621 (나만 안되는 연애) - java

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

14621번: 나만 안되는 연애

MST의 응용 문제이다. 우선 구해야 하는 사심 경로의 조건을 살펴볼 필요가 있다.

1. 사심 경로는 사용자들의 사심을 만족시키기 위해 남초 대학교와 여초 대학교들을 연결하는 도로로만 이루어져 있다.
2. 사용자들이 다양한 사람과 미팅할 수 있도록 어떤 대학교에서든 모든 대학교로 이동이 가능한 경로이다. (연결 그래프라는 뜻)
3.  경로의 길이는 최단 거리가 되어야 한다.

즉 만들어진 MST에 같은 유형 (남 - 남 or 여 - 여) 간선은 포함되서는 안된다는 것이다.

문제를 해결하기 위해 애초에 우선순위 큐에 간선을 추가할 때 다른 유형의 입력값만 추가했다.

 

우선순위 큐 작업

for(int i=1;i<=m;i++)
        {
            st = new StringTokenizer(br.readLine(), " ");
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());
            int val = Integer.parseInt(st.nextToken());

            if(isMen[x] != isMen[y])
            {
                pq.add(new Edge(x,y,val));
            }
        }

 

크루스컬 알고리즘 -> MST 생성

int cost = 0;
while(!pq.isEmpty())
{
   Edge cur = pq.poll();

   if(find(cur.x) != find(cur.y))
   {
      cost += cur.val;
      union(cur.x, cur.y);
      check[cur.x] = true;
      check[cur.y] = true;
    }
}

주의 !

해당 조건에서 사심 경로가 만들어지지 않는 조건은 뭘까? -> MST에 모든 정점이 포함되지 못하는 경우

예를 들어 1번 노드가 남초라고 할 때 1번 노드와 연결된 모든 간선들은 남초하고만 되어있다면 ..... MST에 1번 노드는 포함되지 못할 것이다.

 

전체 코드

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

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

        boolean[] isMen = new boolean[n+1];
        boolean[] check = new boolean[n+1];

        root = new int[n+1];
        for(int i=1;i<=n;i++)
        {
            root[i] = i;
        }

        st = new StringTokenizer(br.readLine(), " ");
        for(int i=1;i<=n;i++)
        {
            String cur =st.nextToken();
            if(cur.equals("M"))
                isMen[i] = true;
        }


        PriorityQueue<Edge> pq = new PriorityQueue<>(
                (x,y) -> x.val - y.val
        );

        for(int i=1;i<=m;i++)
        {
            st = new StringTokenizer(br.readLine(), " ");
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());
            int val = Integer.parseInt(st.nextToken());

            if(isMen[x] != isMen[y])
            {
                pq.add(new Edge(x,y,val));
            }
        }

        int cost = 0;
        while(!pq.isEmpty())
        {
            Edge cur = pq.poll();

            if(find(cur.x) != find(cur.y))
            {
                cost += cur.val;
                union(cur.x, cur.y);
                check[cur.x] = true;
                check[cur.y] = true;
            }
        }

        if(cost==0 || !allCheck(check))
        {
            System.out.println(-1);
        }

        else{
            System.out.println(cost);
        }
        br.close();
    }

    static boolean allCheck(boolean[] arr)
    {
        for(int i=1;i<=n;i++)
        {
            if(!arr[i])
                return false;
        }

        return true;
    }

    static int find(int x)
    {
        if(root[x] == x)
            return x;

        else{
            return root[x] = find(root[x]);
        }
    }

    static void union(int x,int y)
    {
        x = find(x);
        y = find(y);

        if(x < y)
            root[y] = x;

        else
            root[x] = y;
    }
}
class Edge{
    int x;
    int y;
    int val;

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