백준 1197 최소 스패닝 트리 [자바]

04 Jun 2022 in Develop / Solving

baekjoon 1197 최소 스패닝 트리

java

문제 분석

• 그래프가 주어졌을 때, 최소 신장 트리 구하기
• 최소 스패닝 트리의 전체 가중치를 출력.

입력조건

정점의 수 V, 간선의 수 E
E개의 줄에 대해{
	정점A, 정점B, 가중치 C
}

풀이과정

• 크루스칼 알고리즘을 이용해 구현.

코드 구성

• 서로소 집합

  public static void union(int x, int y) {
      p[parent(y)] = parent(x); 
  }
  public static int parent(int x) {
      if( p[x] == x) {
          return x;
      }else {
          return p[x] = parent(p[x]);
      }
  }
  

• 크루스칼 알고리즘

  PriorityQueue<vertex> pq = new PriorityQueue<>();
  for(int i = 0; i < E; i++) {
      st = new StringTokenizer(br.readLine());
      int u = Integer.parseInt(st.nextToken());
      int v = Integer.parseInt(st.nextToken());
      int w = Integer.parseInt(st.nextToken());
    
      pq.add(new vertex(u, v, w));
  }
  p = new int[V+1];
  for(int i = 0; i <= V; i++) p[i] = i;
    
  int selcount = 0;
  int totalw = 0;
  while(selcount < V-1) {
      vertex now = pq.poll();
    
      // 같은 집합이면 넘어가기
      if(parent(now.u) == parent(now.v)) continue;
    
      // 합치기
      union(now.u, now.v);
      selcount++;
      totalw += now.w;
  }
  

전체 코드

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

public class BJ1197_최소스패닝트리 {
	public static class vertex implements Comparable<vertex> {
		int u, v, w;
		vertex(int u, int v, int w){
			this.u = u;
			this.v = v;
			this.w = w;
		}
		@Override
		public int compareTo(vertex o) {
			return this.w - o.w;
		}
		
	}
	static int[] p;
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int V = Integer.parseInt(st.nextToken());
		int E = Integer.parseInt(st.nextToken());
		
		PriorityQueue<vertex> pq = new PriorityQueue<>();
		for(int i = 0; i < E; i++) {
			st = new StringTokenizer(br.readLine());
			int u = Integer.parseInt(st.nextToken());
			int v = Integer.parseInt(st.nextToken());
			int w = Integer.parseInt(st.nextToken());

			pq.add(new vertex(u, v, w));
		}
		p = new int[V+1];
		for(int i = 0; i <= V; i++) p[i] = i;
		
		int selcount = 0;
		int totalw = 0;
		while(selcount < V-1) {
			vertex now = pq.poll();
			
			// 같은 집합이면 넘어가기
			if(parent(now.u) == parent(now.v)) continue;
			
			// 합치기
			union(now.u, now.v);
			selcount++;
			totalw += now.w;
		}
		System.out.println(totalw);
	}
	public static void union(int x, int y) {
		p[parent(y)] = parent(x); 
	}
	public static int parent(int x) {
		if( p[x] == x) {
			return x;
		}else {
			return p[x] = parent(p[x]);
		}
	}
}