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

🔗 문제

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

 

 

 

✏️ 풀이

문제를 풀기 위해선 어떤 조건으로 무엇을 구해야하는지 문제를 잘 봐야합니다!

해당 문제는 설명에 어떤 알고리즘으로 풀어라 힌트를 주고 있습니다. 

 

 

[문제 조건]

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

 

굵은 선으로 처리한 모든 조건들이 최소 신장 트리라고 외치고 있네요.

대표적으로 프림, 크루스칼이 있지만 저는 프림이 잘 기억나지 않아 크루스칼로 풀었습니다.

당연한 거지만 (나 바보 아님) 예전에 정희에게 N개의 정점을 이으려면 N-1개만큼만 이으면 된다는 사실을 배웠기 때문에 써먹었습니다 :)

 

크루스칼에서 모든 pq의 원소를 소모하지 않고, cnt가 N-1면 바로 반복문을 종료해주고 정답을 출력해주었습니다.

주의할 것은 주어주는 입력 데이터는 두 노드의 성별이 같을 수도 있기 때문에 입력을 받을 때 확인을 해주어야 한다는 것입니다.

개인적으로 골3 짜리는 아닌 것 같다라는 소견을 남기며 총총..

---

크루스칼을 처음 배울 때 pq로 배워서 pq를 썼는데, 새로 들어온 스터디원이 좋은 조언을 줬다.

문제 풀이에서 정렬은 단 한번만 필요하므로 굳이 pq를 쓰지 않아도 된다는거였다.

당연한건데 전혀 모르고 있었다!!!!!!!!

정답과 무관하지만 한번도 의심하지 못한 내용이라 이렇게 풀이를 써봤다..

 

 

💾  소스

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

public class Main {

    static int[] root;
    static int find(final int x)
    {
        if(root[x] < 0) return x;
        return root[x] = find(root[x]);
    }

    static boolean merge(final int x, final int y)
    {
        int r1 = find(x);
        int r2 = find(y);

        if(r1==r2) return false;

        if(root[r1] < root[r2])
        {
            root[r2] += root[r1];
            root[r1] = r2;
        }else{
            root[r1] += root[r2];
            root[r2] = r1;
        }

        return true;
    }

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int answer = 0;
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());

        root = new int[N+1];
        Arrays.fill(root, -1);

        char info[] = new char[N+1];
        st = new StringTokenizer(br.readLine());
        for(int i=0; i<N; ++i)
        {
            info[i] = st.nextToken().charAt(0);
        }
        int from, to, weight;

        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> Integer.compare(a[2], b[2]));

        for(int i=0; i<M; ++i)
        {
            st = new StringTokenizer(br.readLine());
            from = Integer.parseInt(st.nextToken());
            to = Integer.parseInt(st.nextToken());
            weight = Integer.parseInt(st.nextToken());

            if(info[from-1] == info[to-1]) // 사용하지 못 하는 도로라 제외
                continue;

            pq.add(new int[] {from, to, weight});
        }

        int cnt = 0;
        int[] top;
        while(!pq.isEmpty())
        {
            top = pq.poll();
            if(merge(top[0], top[1]))
            {
                //System.out.println(Arrays.toString(top));
                answer += top[2];
                if(++cnt == N-1)
                    break;
            }
        }

        System.out.print(cnt==N-1 ? answer : -1);
    } // main
}