[백준/1922] 네트워크 연결 (Java)

Question

• 문제 링크 : https://www.acmicpc.net/problem/1922
• 분류 : 그래프 탐색
• 풀이 시간 : 10분

문제 해설

1. 모든 컴퓨터를 연결하는 네트워크 구축하려고 함
2. 모든 컴퓨터를 연결하는데 필요한 최소비용은?
3. 모든 컴퓨터 연결할 수 없는 경우 없음

Solution

풀이 접근 방법

1. 모든 노드를 연결해야한다, 최소 비용으로 -> 최소 비용 신장 트리 선택 알고리즘 사용(크루스칼, 프림)
2. 해당 풀이는 크루스칼 알고리즘 사용
   1. 가중치를 기준으로 오름차순 정렬
   2. 가중치가 가장 낮은 두 정점 선택
   3. 두 개의 정점이 부모가 같은지 보고(union-find 활용) 다르면 같은 부모로 합침 -> 해당 연결선 선택

정답 코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {
  static class Line implements Comparable<Line> {
    int n1, n2, cost;

    public Line(int n1, int n2, int cost) {
      this.n1 = n1;
      this.n2 = n2;
      this.cost = cost;
    }

    @Override
    public int compareTo(Line o) {
      // 두 컴퓨터를 연결하는 경로의 값을 기준으로 오름차순 정렬
      return Integer.compare(this.cost, o.cost);
    }
  }

  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

    int N = Integer.valueOf(br.readLine());
    int M = Integer.valueOf(br.readLine());
    StringTokenizer st;
    PriorityQueue<Line> lines = new PriorityQueue<Line>();

    while (M-- > 0) {
      st = new StringTokenizer(br.readLine());

      int n1 = Integer.valueOf(st.nextToken());
      int n2 = Integer.valueOf(st.nextToken());
      int cost = Integer.valueOf(st.nextToken());

      lines.add(new Line(n1, n2, cost));
    }

    int total = findMST(N, lines);

    bw.write(total + "\n");
    bw.flush();
    bw.close();

  }

  static int findMST(int N, PriorityQueue<Line> lines) {
    // 특정 노느의 부모를 담는 배열 선택
    int[] parent = new int[N + 1];
    int total = 0;

    // 자기 자신 노드의 부모는 자기 자신으로 초기화
    for (int i = 0; i <= N; i++) {
      parent[i] = i;
    }

    while (!lines.isEmpty()) {
      Line temp = lines.poll();

      // find
      // 각 노드의 부모 탐색
      int n1Parent = getParent(parent, temp.n1);
      int n2Parent = getParent(parent, temp.n2);

      if (n1Parent != n2Parent) {
        // union
        // 부모가 다른 두 노드를 하나의 공통 부모를 가지도록 합침
        parent[n2Parent] = n1Parent;
        // 연결선 선택
        total += temp.cost;
      }
    }

    return total;
  }

  static int getParent(int[] parent, int target) {
    // 부모의 값 = 자기 자신의 값 = 아직 선택되지 않은 노드
    if (parent[target] == target) {
      return target;
    }
    // 부모의 부모까지 찾아서 최종 부모 선택
    return parent[target] = getParent(parent, parent[target]);
  }

}