최소 신장 트리 적용하기

이제 최소 신장 트리에 대해 이해했다면, 실제 문제를 풀면서 학습할 차례다.

위 문제를 여러 알고리즘으로 풀면서 익혀보자.

먼저 떠올린건 크루스칼이었다. 상대적으로 구현이 쉬우므로 먼저 구현했다.

• 크루스칼

  import java.io.*;
  import java.util.*;
  
  public class Main {
      static class Edge implements Comparable<Edge> {
          int src, dst, cost;
  
          public Edge(int _src, int _dst, int _cost) {
              src = _src;
              dst = _dst;
              cost = _cost;
          }
  
          public int compareTo(Edge e) {
              return cost - e.cost;
          }
      }
  
      static class UnionFinder {
          int[] parent;
          int[] rank;
  
          public UnionFinder(int n) {
              parent = new int[n + 1];
              rank = new int[n + 1];
              for (int i = 0; i <= n; i++) {
                  parent[i] = i;
                  rank[i] = 0;
              }
          }
  
          public int find(int x) {
              if (parent[x] != x) {
                  parent[x] = find(parent[x]);
              }
              return parent[x];
          }
  
          public void union(int x, int y) {
              int xroot = find(x);
              int yroot = find(y);
  
              if (xroot == yroot)
                  return;
  
              int cmp = compareRank(xroot, yroot);
              if (cmp < 0) {
                  parent[xroot] = yroot;
              } else if (cmp > 0) {
                  parent[yroot] = xroot;
              } else {
                  parent[yroot] = xroot;
                  rank[xroot]++;
              }
          }
  
          public int compareRank(int x, int y) {
              return rank[x] - rank[y];
          }
      }
  
      public static void main(String[] args) throws Exception {
          BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
  
          int N = Integer.parseInt(br.readLine());
  
          PriorityQueue<Edge> pq = new PriorityQueue<>();
          for (int i = 0; i < N; i++) {
              int cost = Integer.parseInt(br.readLine());
              pq.add(new Edge(N, i, cost));
          }
  
          for (int i = 0; i < N; i++) {
              String[] tokens = br.readLine().split(" ");
              for (int j = i + 1; j < N; j++) {
                  pq.add(new Edge(i, j, Integer.parseInt(tokens[j])));
              }
          }
  
          int answer = 0;
          UnionFinder uf = new UnionFinder(N);
          while (!pq.isEmpty()) {
              Edge edge = pq.poll();
              int xroot = uf.find(edge.src);
              int yroot = uf.find(edge.dst);
  
              if (xroot != yroot) {
                  answer += edge.cost;
                  uf.union(xroot, yroot);
              }
          }
  
          System.out.println(answer);
      }
  }
  

단순 알고리즘 구현이 아닌, 별도의 루트노트를 가정하여 간선을 추가하는 방식으로 풀 수 있다.

또한 코드에서 간선 중심으로 작성되어있는 것을 볼 수 있다.

다음은 프림으로 풀어보자. 프림은 노드 중심이므로, 별도의 루트를 시작점으로 제시하면 된다.

• 프림

  import java.io.*;
  import java.util.*;
  
  public class Main {
      static class Edge implements Comparable<Edge> {
          int node, cost;
  
          public Edge(int _node, int _cost) {
              node = _node;
              cost = _cost;
          }
  
          public int compareTo(Edge e) {
              return cost - e.cost;
          }
      }
  
      public static void main(String[] args) throws IOException {
          BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
          int N = Integer.parseInt(br.readLine());
  
          List<Edge>[] graph = new ArrayList[N + 1];
          for (int i = 0; i <= N; i++) {
              graph[i] = new ArrayList<>();
          }
  
          for (int i = 1; i <= N; i++) {
              int cost = Integer.parseInt(br.readLine());
              graph[0].add(new Edge(i, cost));
              graph[i].add(new Edge(0, cost));
          }
  
          for (int i = 1; i <= N; i++) {
              String[] tokens = br.readLine().split(" ");
              for (int j = 1; j <= N; j++) {
                  int cost = Integer.parseInt(tokens[j - 1]);
                  if (i != j) {
                      graph[i].add(new Edge(j, cost));
                  }
              }
          }
  
          boolean[] visited = new boolean[N + 1];
          PriorityQueue<Edge> pq = new PriorityQueue<>();
          pq.add(new Edge(0, 0));
          int totalCost = 0;
  
          while (!pq.isEmpty()) {
              Edge curr = pq.poll();
              int node = curr.node;
              int cost = curr.cost;
  
              if (visited[node])
                  continue;
              visited[node] = true;
              totalCost += cost;
  
              for (Edge next : graph[node]) {
                  if (!visited[next.node]) {
                      pq.add(new Edge(next.node, next.cost));
                  }
              }
          }
  
          System.out.println(totalCost);
      }
  }

실전성을 떨어진다고 하지만, 배운김에 보루프카도 적용해보자.

• 보르푸카

  import java.io.*;
  import java.util.*;
  
  public class Main {
      static class Edge {
          int src, dst, cost;
  
          public Edge(int _src, int _dst, int _cost) {
              src = _src;
              dst = _dst;
              cost = _cost;
          }
      }
  
      static class Boruvka {
          int[] parent;
  
          public Boruvka(int n) {
              parent = new int[n + 1];
              for (int i = 0; i <= n; i++) {
                  parent[i] = i;
              }
          }
  
          public int find(int x) {
              if (parent[x] != x) {
                  parent[x] = find(parent[x]);
              }
              return parent[x];
          }
  
          public boolean union(int x, int y) {
              int xroot = find(x);
              int yroot = find(y);
  
              if (xroot == yroot)
                  return false;
              parent[yroot] = xroot;
              return true;
          }
      }
  
      public static void main(String[] args) throws IOException {
          BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
          int N = Integer.parseInt(br.readLine());
  
          List<Edge> edges = new ArrayList();
  
          for (int i = 1; i <= N; i++) {
              int cost = Integer.parseInt(br.readLine());
              edges.add(new Edge(0, i, cost));
          }
  
          for (int i = 1; i <= N; i++) {
              String[] tokens = br.readLine().split(" ");
              for (int j = 1; j <= N; j++) {
                  if (i != j) {
                      int cost = Integer.parseInt(tokens[j - 1]);
                      edges.add(new Edge(i, j, cost));
                  }
              }
          }
  
          int tot = 0;
          Boruvka bv = new Boruvka(N);
          int components = N + 1;
  
          while (components > 1) {
              Edge[] minEdge = new Edge[N + 1];
  
              for (Edge e : edges) {
                  int u = bv.find(e.src);
                  int v = bv.find(e.dst);
  
                  if (u == v)
                      continue;
  
                  if (minEdge[u] == null || minEdge[u].cost > e.cost) {
                      minEdge[u] = e;
                  }
                  if (minEdge[v] == null || minEdge[v].cost > e.cost) {
                      minEdge[v] = e;
                  }
              }
  
              for (int i = 0; i <= N; i++) {
                  Edge e = minEdge[i];
                  if (e != null && bv.union(e.src, e.dst)) {
                      tot += e.cost;
                      components--;
                  }
              }
          }
  
          System.out.println(tot);
      }
  }
  

세 알고리즘의 결과는 위에서 부터 보르푸카, 프림, 크루스칼의 순서로 아래와 같이 나타난다.

보르푸카의 실전성은 떨어지지만 성능적인 면에서 우수한 점이 돋보인다고 할 수 있다.