백준 1647 도시 분할 계획 [자바]

04 Jun 2022 in Develop / Solving

baekjoon 1647 도시 분할 계획

java

문제 분석

• 집끼리 최소 길이로 연결할거임.
• 연결된 최소 길이를 출력.

입력조건

집의 개수 N, 길의 개수 M
M개의 줄에 대해{
	정점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]);
  }
  

• 크루스칼 알고리즘 but 간선을 하나 덜 선택.

  PriorityQueue<vertex> pq = new PriorityQueue<>();
  for(int i = 0; i < M; 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[N+1];
  for(int i = 0; i <= N; i++) p[i] = i;
    
  int selcount = 0;
  long cost = 0;
  while(selcount < N-2) {
      vertex now = pq.poll();
    
      if(parent(now.u) == parent(now.v)) continue;
    
      union(now.u, now.v);
      cost += now.w;
      selcount++;
  }
  

전체 코드

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

public class BJ1647_도시분할계획 {
	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 N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());
		
		PriorityQueue<vertex> pq = new PriorityQueue<>();
		for(int i = 0; i < M; 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[N+1];
		for(int i = 0; i <= N; i++) p[i] = i;
		
		int selcount = 0;
		long cost = 0;
		while(selcount < N-2) {
			vertex now = pq.poll();
			
			if(parent(now.u) == parent(now.v)) continue;
			
			union(now.u, now.v);
			cost += now.w;
			selcount++;
		}
		System.out.print(cost);
	}
	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]);
	}
}