kruskal2 [백준] BOJ2211네트워크 복구 https://www.acmicpc.net/problem/2211 네트워크 복구라는 문제인데 해당 문제를 풀기 위해 아래 2가지 알고리즘을 사용했다. 1) 다익스트라 2) 프림 import java.io.BufferedReader; import java.io.FileInputStream; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.Arrays; import java.util.Comparator; import java.util.LinkedList; import java.util.PriorityQueue; import java.util.Queue; import java.util.StringTokenizer; p.. 2018. 9. 25. [백준] BOJ1922 네트워크 연결 - MST(최소신장트리) - 크루스칼 알고리즘 MST (Minimum Spanning Tree) - Kruskal 알고리즘 MST 란 모든 노드를 최소 비용으로 연결하는 알고리즘인데, 아래의 조건을 만족해야 한다. 1) 싸이클이 없어야 하고 2) 모든 노드가 연결되어야 한다. 이 때, a 노드에서 b 노드로 연결되어 있고, b 노드에서 c 노드로 연결되어 있다면, a 노드에서 c 노드로 연결되어 있다고 할 수 있다. Kruskal 알고리즘- 준비 // 간선을 가중치 기준으로 오름차순 정렬한다. // 모든 점을 하나의 트리로 설정한다. (Union & Find 기법 사용) - 시작 // 가중치가 작은 간선부터 하나씩 본다. // 해당 간선을 그래프에 추가할 때 싸이클이 생기지 않는다면 해당 간선을 그래프에 추가한다. 백준 BOJ1922 문제를 풀기 위.. 2018. 9. 16. 이전 1 다음