다리만들기 2 DFS 와 MST를 이용한 풀이. DFS로 섬의 개수와 위치를 파악하고 크루스칼을 사용하여 풀이 하였음. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.Collections; import java.util.StringTokenizer; public class 다리만들기2_17472 { static int N, M, map[][], index = 2, parents[]; static int[] dr = { -1, 1, 0, 0 }; static int[] dc = { 0, 0, -1, 1 }; ..
프림과 크루스칼을 이용한 MST 구하는 문제 프림과 크루스칼의 차이 : 프림은 정점의 리스트를 크루스칼은 간선의 리스트를 저장해야 한다!! ※ 간만프 간적쿠 (공식처럼 외우기) * 프림과 다익스트라 코드가 비슷하니 잘 이해하고 넘어가자 Prim import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.Arrays; import java.util.PriorityQueue; import java.util.StringTokenizer; public class 하나로_prim { static int T, N, arr[][];..
다익스트라 알고리즘을 활용한 풀이 * 다익스트라 코드와 프림코드가 상당히 유사함. dis배열의 값을 갱신할 때, 더해서 넣냐 그냥 최소값만 넣냐 차이. (더해서 넣는 경우가 다익스트라) import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.Arrays; import java.util.PriorityQueue; import java.util.StringTokenizer; public class 최단경로_1753 { static int V, E, start; static ArrayList[] list; static c..
Kruskal은 간선리스트, Prim은 정점리스트를 사용한다. Kruskal 알고리즘 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.Arrays; import java.util.Collection; import java.util.Collections; import java.util.StringTokenizer; public class 최소스패닝트리_1197_kruskal { static int V, E, parents[]; static class Point implements Comparable { int ..
알고리즘 풀이 dfs는 100x100이라 힘들다.. bfs로 풀어야 하는데 최단거리가 아닌 값이 가장 작은 수를 구해야 함. 값을 더해가면서 저장하는데 값이 가장 작은 것부터 계속 더해 나가야 하기 때문에 우선순위 큐를 사용하여 더한 값이 작은 순으로 실행. 결론에 도달했을 때는 가장 작은 값이 저장 됨 -> 정답 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.PriorityQueue; public class 보급로 { static int T, N, map[][], Ans = Integer.MAX_VALUE; static boolean[][] v; stat..