[BOJ] 1197.최소 스패닝 트리(MST, prim, kruskal).java

#. Problem

https://www.acmicpc.net/problem/1197

* The copyright in this matter is in BOJ

#. Resolution Process

  1. Read and understand problem

  2. Redefine the problem + abstract

  3. Create solution plan (select Algorithm, Data structure)

  4. Prove the plan (check performance time and usage memory)

  5. Carry out the plan

  6. Look back on the plan and find a way to improve it

#. Solve

  

그래프가 주어졌을 때, 그 그래프의 최소 스패닝 트리를 구하는 프로그램을 작성하시오.

최소 스패닝 트리는, 주어진 그래프의 모든 정점들을 연결하는 부분 그래프 중에서 그 가중치의 합이 최소인 트리를 말한다.

문제 그대로 MST 알고리즘을 적용해보는 문제이다.

MST 하면 간적크, 간만프를 생각해야 한다.

간선이 적으면 크루스칼, 간선이 많으면 프림

단, 절대적인 것은 아니라는 것!

무방향 그래프에서 

최대 간선의 개수는 V(V-1)/2 개 이다.

그러므로 이 문제에서 나올 수 있는 최대 간선의 개수는 V(1 ≤ V ≤ 10,000) V가 10,000 일 때,

10,000 x 9,999 / 2 = 49,995,000 개가 된다.

다행히 문제에서는 간선의 개수 E(1 ≤ E ≤ 100,000) 범위를 지정해주어서

크루스칼 알고리즘을 적용했을 때 더 유리할 것 같다.

하지만, 뭐라고~? 절대적인 것은 아니라는 것!

#. Code_Prim

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88

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 BOJ1197 {       static int V, E;     static ArrayList<Node>[] adj;     static class Node implements Comparable<Node> {         int to, weight;           public Node(int to, int weight) {             super();             this.to = to;             this.weight = weight;         }           @Override         public int compareTo(Node o) {             return Integer.compare(this.weight, o.weight);         }              }          public static void main(String[] args) throws IOException {                  BufferedReader br = new BufferedReader(new InputStreamReader(System.in));         StringTokenizer st = new StringTokenizer(br.readLine());           V = Integer.parseInt(st.nextToken());    // 정점 개수         E = Integer.parseInt(st.nextToken());    // 간선 개수                  adj = new ArrayList[V + 1];         for (int i = 1; i <= V; i++) {             adj[i] = new ArrayList<>();         }                  // Edge 정보 입력         for (int i = 0; i < E; i++) {             st = new StringTokenizer(br.readLine());             int a = Integer.parseInt(st.nextToken());             int b = Integer.parseInt(st.nextToken());             int c = Integer.parseInt(st.nextToken());             // 인접 리스트             adj[a].add(new Node(b, c));             adj[b].add(new Node(a, c));         }                  System.out.println(prim());     }       private static long prim() {                  boolean[] visited = new boolean[V + 1];         PriorityQueue<Node> pq = new PriorityQueue<>();         // 1번 노드부터 출발         pq.add(new Node(1, 0));                  long res = 0;         int cnt = 0;         while(!pq.isEmpty()) {                          Node edge = pq.poll();             // 이미 확인한 정점이면 pass             if(visited[edge.to]) continue;                          res += edge.weight;             visited[edge.to] = true;             // 모든 노드를 방문했다면 return             if(++cnt == V) return res;                          for (int i = 0; i < adj[edge.to].size(); i++) {                 // 연결된 노드들 중 방문하지 않은 노드 찾기                 Node next = adj[edge.to].get(i);                  if(visited[next.to]) continue;                                  pq.add(next);             }         }                  return res;     }   }   Colored by Color Scripter

cs

#. Code_Kruskal

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97

import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Arrays; import java.util.StringTokenizer;   public class BOJ1197_v2 {       static int V, E, parents[];     static Edge[] edgeList;          static class Edge implements Comparable<Edge> {         int from, to, weight;           public Edge(int from, int to, int weight) {             super();             this.from = from;             this.to = to;             this.weight = weight;         }           @Override         public int compareTo(Edge o) {             return Integer.compare(this.weight, o.weight);         }              }          public static void main(String[] args) throws IOException {                  BufferedReader br = new BufferedReader(new InputStreamReader(System.in));         StringTokenizer st = new StringTokenizer(br.readLine());           V = Integer.parseInt(st.nextToken());    // 정점 개수         E = Integer.parseInt(st.nextToken());    // 간선 개수                  edgeList = new Edge[E];         parents = new int[V + 1];           // Edge 정보 입력         for (int i = 0; i < E; i++) {             st = new StringTokenizer(br.readLine());             int a = Integer.parseInt(st.nextToken());             int b = Integer.parseInt(st.nextToken());             int c = Integer.parseInt(st.nextToken());                          edgeList[i] = new Edge(a, b, c);         }                  System.out.println(kruskal());     }       private static int kruskal() {                  int res = 0, cnt = 0;                  // 간선 가중치 기준 오름차순 정렬         Arrays.sort(edgeList);         // 정점 초기화         make();                  // 주어진 간선을 이어보면서         for (Edge edge : edgeList) {             // 싸이클이 형성되지 않는다면             if(union(edge.from, edge.to)) {                 // 해당 간선을 사용                 res += edge.weight;                 // 정점 - 1 개의 간선이 이어졌다면 MST 완성!                 if(++cnt == V - 1) return res;             }         }                  return res;     }       private static boolean union(int a, int b) {         int aRoot = find(a);         int bRoot = find(b);                  if(aRoot == bRoot) return false;         parents[aRoot] = bRoot;         return true;     }       private static int find(int a) {         if(a == parents[a]) return a;         return parents[a] = find(parents[a]);     }       private static void make() {         for (int i = 1; i <= V; i++) {             parents[i] = i;         }     }   }   Colored by Color Scripter

cs