📙[Algo] 24.04.26 알고리즘

알고리즘 문제) BOJ 14621. 나만 안되는 연애

14621번: 나만 안되는 연애

문제 요약

• 아래 조건을 만족하는 경로의 총 길이 구하기
  • 남초 대학교와 여초대학교를 연결하는 도로로만 구성
  • 어떤 대학교에서든 모든 대학교로 이동 가능해야함
  • 최단 거리가 될 것

시간 제한

• 2초

입력

• 학교 수 N, 도로 수 M
  • 2 ≤ N ≤ 1000
  • 1 ≤ M ≤ 10000
• 각 학교가 남초 대학교면 M, 여초 대학교면 W
• M개의 줄에 u v d가 주어짐
  • u학교와 v학교가 연결되어있으며, 거리가 d
  • 1 ≤ u,v ≤ N, 1 ≤ d ≤ 1000

출력

• 조건을 만족하는 경로의 총 길이 출력
• 만약 모든 학교를 여결하는 경로가 없다면 -1 출력

접근법

• 남초대와 여초대를 인접시키며, MST를 구성하는 문제

코드

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

public class Main {
    static int N, M;
    static char[] info;
    static int[] parent;
    static int[][] graph;

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

        parent[x] = find(parent[x]);
        return parent[x];
    }

    static void union(int a, int b) {
        a = find(a);
        b = find(b);

        if (a == b) return;

        parent[b] = a;
    }


    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());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

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

        parent = new int[N + 1];
        for (int i = 0; i < N + 1; i++) {
            parent[i] = i;
        }

        graph = new int[M][3];
        int v1, v2, d;
        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            v1 = Integer.parseInt(st.nextToken());
            v2 = Integer.parseInt(st.nextToken());
            d = Integer.parseInt(st.nextToken());

            graph[i][0] = v1;
            graph[i][1] = v2;
            graph[i][2] = d;
        }

        Arrays.sort(graph, new Comparator<int[]>(){
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[2] - o2[2];
            }
        });

        int cnt = 1, answer = 0;
        for (int i = 0; i < M; i++) {
            v1 = graph[i][0];
            v2 = graph[i][1];
            d = graph[i][2];

            if (find(v1) == find(v2)) continue;

            if (info[v1] == info[v2]) continue;

            union(v1, v2);
            cnt++;
            answer += d;
        }

        if (cnt < N) bw.write("-1");
        else bw.write(String.valueOf(answer));

        bw.flush();
        bw.close();
        br.close();
    }
}