03.31 학습&숙제

썸네일 출처

PRIM! 🟥🟧🟨🟩🟦🟪🟫⬜⬛🫢🔔😎😊🤔😭⭐

---

PRIM 알고리즘

1. 임의 정점을 하나 선택해서 시작
2. 선택한 정점과 인접하는 정점들 중의 최소 비용의 간선이 존재하는 정점을 선택
3. 모든 정점이 선택될 때까지 2 과정을 반복

서로소인 2개의 집합(2 disjoint-sets) 정보를 유지

---

백준 17490번 일감호에 다리 놓기

정답코드

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



public class Main {
	static int n; // 강의동의 수 <= 1,000,000
	static int m; // 공사구간의 수  <= 1,000,000
	static long k; // 돌의 수 <= 5,000,000,000
	static int[] arr; // 각각의 동과 놓아야 하는 돌  1,000,000
	static int[] p; // union-find 재료	
	static int[] visited; // 공사중 인 곳 
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		
		st = new StringTokenizer(br.readLine());
		n = Integer.parseInt(st.nextToken());
		m = Integer.parseInt(st.nextToken());
		k = Long.parseLong(st.nextToken());
		arr = new int[n+1];
		p = new int[n+1];
		visited = new int[n+1];
		
		st = new StringTokenizer(br.readLine());
		for(int i=1;i<=n;i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}
		for(int i=0;i<m;i++) {
			st = new StringTokenizer(br.readLine());
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			visited[b] = 1;
		}
		for(int i=1;i<=n;i++) {
			p[i] = i;
		}
		
		// 옆의 강의동과 연결 hash에 있는 곳만 빼고 
		for(int i=1;i<=n;i++) {
			int a = i;
			int b = i != n ? i+1 : 1;
			if(visited[b] == 1) continue;
			union(a,b);
		}
		// 가장 적은 돌이 필요한 공사구간이 대표이므로 대표들의 합을 구한다  
		long sum = 0;
		for(int i=1;i<=n;i++) {
			if(p[i] == i) {
				sum += arr[i];
			}
		}
		// 공사 중인 곳이 하나거나 없으면 다 이어져있는 것 예외처리!
		if(sum <= k || m <= 1) {
			System.out.println("YES");
		}
		else {
			System.out.println("NO");
		}
	
		
	}
	private static void union(int a, int b) {
		int A = find(a);
		int B = find(b);
		if(A == B) return;
		// 값이 작으면 대표! 
		if(arr[A] < arr[B]) {
			p[B] = A;
		}
		else {
			p[A] = B;
		}
	}
	private static int find(int a) {
		if(p[a] == a) return a;
		else return p[a] = find(p[a]);
	}
}

풀이

유니온 파인드의 대표를 고르는 방법을 작은 돌이 필요한 노드를 대표로 하여 최소값을 찾아준다!
공사중인 장소가 0이거나 하나라면 다 연결된다는 점을 예외처리!

숙제

알고리즘 1개 , VS 시리즈 1개