최소 신장 트리 > 14621번, 14950번, 21924번

14621번

 

// 모든 대학교 간 이동이 가능해야 함
// 최단 경로
// 크루스칼 알고리즘 사용

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

public class baekjoon14621 {

    static int n; // 학교 수 (1번 대학교, 2번 대학교...)
    static int m; // 연결하는 도로 수
    static Map<Integer, String> map = new HashMap<>();
    static ArrayList<Application> [] lists; // 인접리스트
    static boolean [] visited; // 방문 여부 체크
    static int result;
    static int count = 0;


    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());
        lists = new ArrayList[n+1];
        visited = new boolean[n+1];
        st = new StringTokenizer(br.readLine(), " ");
        for(int i = 0; i<n; i++) {
            map.put(i+1, st.nextToken()); // 대학교 번호와 대학교가 남초인지 여초인지 담아줌
        }
        for(int i = 1; i<n+1; i++) {
            lists[i] = new ArrayList<>();
        }
        for(int i = 0; i<m; i++) {
            st = new StringTokenizer(br.readLine()," ");
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            int distance = Integer.parseInt(st.nextToken());
            lists[a].add(new Application(b, map.get(b), distance)); // 양방향 이동 가능
            lists[b].add(new Application(a, map.get(a), distance));
        }
        prim(1);
        if(count == n) { // 모든 대학교가 연결되어 있다면
            System.out.println(result);
        } else {
            System.out.println(-1);
        }
    }
    public static void prim (int x) {
        PriorityQueue<Application> queue = new PriorityQueue<>();
        queue.offer(new Application(x, map.get(x),0));
        while(!queue.isEmpty()) {
            Application application = queue.poll();
            if(!visited[application.num]) {
                visited[application.num] = true;
                result += application.distance;
                count++; // 방문 처리된 대학교가 몇 개인지
                for(Application next : lists[application.num]) {
                    if(!application.gender.equals(map.get(next.num))) { // 성별이 다른 경우에만 연결될 수 있음
                        queue.offer(new Application(next.num, map.get(next.num), next.distance));
                    }
                }
            }
        }
    }
}

class Application implements Comparable<Application>{

    int num;
    String gender;
    int distance;

    public Application(int num, String gender, int distance) {
        this.num = num;
        this.gender = gender;
        this.distance = distance;
    }

    @Override
    public int compareTo(Application a) {
        return this.distance-a.distance; // 경로 오름차순 정렬
    }
}

 

14950번

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class baekjoon14950 {

    static int n; // 도시의 개수
    static int m; // 도로의 개수
    static int t; // 한번 정복할 때마다 증가하는 도로의 비용
    static ArrayList<Conquer> [] lists; // 인접 리스트
    static boolean [] visited; // 방문 여부 확인
    static int total = 0;
    static int count = 0;

    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());
        t = Integer.parseInt(st.nextToken());
        lists = new ArrayList[n+1];
        visited = new boolean[n+1];
        for(int i = 1; i<n+1; i++) {
            lists[i] = new ArrayList<>();
        }
        for(int i = 0; i<m; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            int cost = Integer.parseInt(st.nextToken());
            lists[a].add(new Conquer(b, cost)); // 도로는 양방향
            lists[b].add(new Conquer(a, cost));
        }
        prim(1);
        System.out.println(total);
    }
    public static void prim (int x) {
        PriorityQueue<Conquer> queue = new PriorityQueue<>();
        queue.offer(new Conquer(x, 0));
        while(!queue.isEmpty()) {
            Conquer conquer = queue.poll();
            if(!visited[conquer.num]) {
                visited[conquer.num] = true;
                if(count <= 1) { // 도로의 비용이 늘어나지 않고 기존의 비용만 더해줌
                    total += conquer.cost;
                } else { // 정복이 된 도시가 하나 이상 존재한 이후부터 도로의 비용이 늘어남
                    total += conquer.cost + (count - 1) * t;
                }
                count++;
                for(Conquer next : lists[conquer.num]) {
                    queue.offer(new Conquer(next.num, next.cost));
                }
            }
        }
    }
}

class Conquer implements Comparable<Conquer>{
    int num;
    int cost;

    public Conquer(int num, int cost) {
        this.num = num;
        this.cost = cost;
    }

    @Override
    public int compareTo(Conquer c) {
        return this.cost-c.cost; // 비용 오름차순 정렬
    }
}

 

21924번

 

// 절약될 수 있는 금액 = 기존에 드는 비용 - 최소 비용
// 양방향 도로
// 정수의 오버플로우에 주의할 것 (비용 계산에 있어 int 범위를 벗어나는 경우 존재)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class baekjoon21924 {

    static int n; // 건물의 개수
    static ArrayList<Road> [] lists; // 인접 리스트
    static int m; // 도로의 개수
    static boolean [] visited; // 방문 여부 확인
    static long minCost;
    static long total;
    static int count = 0;

    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());
        lists = new ArrayList[n+1];
        visited = new boolean[n+1];
        for(int i = 1; i<n+1; i++) {
            lists[i] = new ArrayList<>();
        }
        for(int i = 0; i<m; i++) {
            st = new StringTokenizer(br.readLine()," ");
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            int cost = Integer.parseInt(st.nextToken());
            lists[a].add(new Road(b, cost));
            lists[b].add(new Road(a, cost));
            total += cost;
        }
        prim(1);
        if(count == n) {
            System.out.println(total-minCost);
        } else { // 모든 건물이 연결되어 있지 않는 경우
            System.out.println(-1);
        }
    }
    public static void prim (int x) {
        PriorityQueue<Road> queue = new PriorityQueue<>();
        queue.offer(new Road(x, 0));
        while(!queue.isEmpty()) {
            Road road = queue.poll();
            if(!visited[road.building]) {
                count++; // 건물 방문 횟수 세기
                visited[road.building] = true;
                minCost += road.cost;
                for(Road next : lists[road.building]) {
                    if(!visited[next.building]) {
                        queue.offer(new Road(next.building, next.cost));
                    }
                }
            }
        }
    }
}

class Road implements Comparable<Road>{
    int building;
    int cost;

    public Road(int building, int cost) {
        this.building = building;
        this.cost = cost;
    }

    @Override
    public int compareTo(Road r) {
        return this.cost-r.cost;
    }
}