Traveling Programmer

문제https://www.acmicpc.net/problem/10423풀이(29분)import java.io.*;import java.util.*;class Main { static int[] parent; static boolean[] hasPower; static int n, m, k, nonLinked, cost; static List edges = new ArrayList(); public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st..

문제https://www.acmicpc.net/problem/1922풀이(15분)import java.io.*;import java.util.*;class Main { static int[] parent; static List nodeList = new ArrayList(); public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st; int n = Integer.parseInt(br.readLine()); parent = ne..

최소 신장 트리(MST)란?최소 신장 트리(Minimum Spanning Tree)를 알기 위해서는 신장 트리(Spanning Tree)가 무엇인지 알아야 한다. 신장 트리(Spanning Tree)위의 그림 그래프에서 아래 그래프 3개 모두 신장 트리(위 그림에 따르면 3개가 더 존재함.)그래프의 모든 정점을 포함하는 트리그래프의 최소 연결 부분 그래프로 사이클이 없음정점의 개수 n개면 간선의 개수 n-1개 가짐(사이클이 존재하지 않기 때문이다.)하나의 그래프에 많은 신장 트리 존재최소 신장 트리(Minimum Spanning Tree)가운데 신장 트리는 신장 트리 중 가중치 합이 가장 최소인 최소 신장 트리신장 트리 중 간선의 가중치 합이 최소인 트리사이클이 없는 그래프 중 최소의 가중치크루스칼(kr..