최소 신장 트리 > 1922번, 1647번, 6497번

최소 신장 트리

 

신장 트리는 그래프의 모든 정점을 연결하는 사이클이 없는 트리이다

최소 신장 트리는 신장 트리 중 정점들을 연결하는 간선들의 합이 최소가 되는 트리이다

 

최소 신장 트리를 구하는 알고리즘에는 프림 알고리즘과 크루스칼 알고리즘이 있다

• 프림 알고리즘

       시작 정점을 기준으로 가장 작은 가중치를 가진 간선을 선택하여 트리를 확장

• 크루스칼 알고리즘

       간선의 가중치를 기준으로 오름차순 정렬 후 가중치가 가장 작은 간선부터 선택하여 선택한

       간선의 두 정점이 연결되어 있지 않으면 연결

 

 

1922번

 

 

마지막에 남아있는 queue는 이미 모두 방문 상태이므로 poll()되고 반복문 종료

 

프림 알고리즘은 다익스트라 알고리즘과 유사하다

 

// 모든 컴퓨터를 연결하는데 필요한 최소 비용
// n = 컴퓨터의 수 = 정점의 개수
// m = 연결할 수 있는 선의 수 = 간선의 개수
// 프림 알고리즘 사용 : 우선순위 큐


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 baekjoon1922 {

    static int n;
    static int m;
    static ArrayList<Computer> [] lists; // 간선 정보 담은 인접리스트
    static boolean [] visited; // 방문 여부 체크
    static int result;


    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        m = Integer.parseInt(br.readLine());
        visited = new boolean[n+1];
        lists = new ArrayList[n+1];
        for(int i = 1; i<n+1; i++) {
            lists[i] = new ArrayList<>();
        }
        for(int i = 0; i<m; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine(), " ");
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            int value = Integer.parseInt(st.nextToken());
            lists[a].add(new Computer(b,value)); // 양방향
            lists[b].add(new Computer(a,value));
        }
        prim(1); // 시작점이 어디여도 상관없다
        System.out.println(result);
    }

    public static void prim (int x) {
        PriorityQueue<Computer> queue = new PriorityQueue<>();
        queue.offer(new Computer(x, 0));
        while(!queue.isEmpty()) {
            Computer computer = queue.poll();
            if(!visited[computer.v1]) {
                visited[computer.v1] = true;
                result += computer.cost;

                for(Computer next : lists[computer.v1]) {
                    if(!visited[next.v1]) {
                        queue.offer(new Computer(next.v1, next.cost));
                    }
                }
            }
        }
    }
}

class Computer implements Comparable<Computer>{
    int v1;
    int cost;

    Computer (int v1, int cost) {
        this.v1 = v1;
        this.cost = cost;
    }

    @Override
    public int compareTo(Computer o) { 
        return this.cost-o.cost; // 비용을 오름차순 기준으로 정렬
    }
}

 

1647번

 

// 집의 개수 = 정점의 개수 = n
// 길의 개수 = 간선의 개수 = m
// 분리된 두 마을 사이에 있는 길은 필요가 없으므로 없앤다
// 나머지 길의 유지비 합을 최소로 하면서 마을을 두 개로 분리
// 최소 신장 트리에서 간선의 길이가 최대인 간선 하나만 없애면 된다

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 beakjoon1647 {

    static int n;
    static int m;
    static ArrayList<Town> [] lists;
    static boolean [] visited;
    static int result;
    static int max = 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());
        visited = new boolean[n+1];
        lists = new ArrayList[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 Town(b, cost));
            lists[b].add(new Town(a, cost));
        }
        prim(1);
        System.out.println(result-max);
    }
    public static void prim (int x) {
        PriorityQueue<Town> queue = new PriorityQueue<>();
        queue.offer(new Town(x, 0));
        while(!queue.isEmpty()) {
            Town town = queue.poll();
            if(!visited[town.num]) {
                visited[town.num] = true;
                result += town.cost;
                if(town.cost > max) {
                    max = town.cost;
                }
                for(Town next : lists[town.num]) {
                    queue.offer(new Town(next.num, next.cost));
                }
            }
        }
    }
}

class Town implements Comparable<Town>{
    int num;
    int cost;
    Town(int num, int cost) {
        this.num = num;
        this.cost = cost;
    }

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

 

6497번

 

 

테스트 케이스를 계속 입력 받으며 절약할 수 있는 최대 비용을 출력하며 0이 두 개 입력되면 종료

 

// 모든 두 집 쌍에 대해 불이 켜진 길만으로 서로를 왕래 (양방향)
// 모든 집들을 지나갈 수 있도록 불이 켜져 있어야 한다
// 집의 개수 = 정점의 개수 = m
// 길의 개수 = 간선의 개수 = n
// 길의 불을 꺼서 절약할 수 있는 최대 액수 = 불이 켜진 길들 최소 거리

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 baekjoon4386 {

    static int m;
    static int n;
    static ArrayList<City>[] lists;
    static boolean[] visited;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        while (true) {
            st = new StringTokenizer(br.readLine(), " ");
            m = Integer.parseInt(st.nextToken());
            n = Integer.parseInt(st.nextToken());
            if (m == 0 && n == 0) {
                break;
            }
            visited = new boolean[m];
            lists = new ArrayList[m];
            for (int i = 0; i < m; i++) {
                lists[i] = new ArrayList<>();
            }
            int sum = 0;
            for (int i = 0; i < n; 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 City(b, cost));
                lists[b].add(new City(a, cost));
                sum += cost;
            }
            System.out.println(sum -  prim(0));
        }
    }

    public static int prim(int x) {
        int total = 0;
        PriorityQueue<City> queue = new PriorityQueue<>();
        queue.offer(new City(x, 0));
        while (!queue.isEmpty()) {
            City city = queue.poll();
            if (!visited[city.num]) {
                visited[city.num] = true;
                total += city.distance;
                for (City next : lists[city.num]) {
                    queue.offer(new City(next.num, next.distance));
                }
            }
        }
        return total;
    }
}

class City implements Comparable<City> {
    int num;
    int distance;

    City(int num, int distance) {
        this.num = num;
        this.distance = distance;
    }

    @Override
    public int compareTo(City o) {
        return this.distance - o.distance; // 거리 오름차순 정렬
    }
}