백준 - 2406 안정적인 네트워크

[문제 바로가기]

 

1. 유형

MST

 

2. 문제 접근

 

2-1. 해설

 

컴퓨터가 고장 난 경우

1. 1번 컴퓨터가 고장남 -> 나머지들이 MST 구조이다

2. 1번을 제외한 컴퓨터가 고장남 -> 어차피 1번과 연결되어 있어서 구할 필요 없음.

 

두 컴퓨터 간 연결이 끊어짐

1. 1번과 그 외의 컴퓨터 간의 연결이 끊어짐 -> 1번을 제외하고 MST 구조를 구해야 함

2. 1번을 제외한 두 컴퓨터 간 연결이 끊어짐 -> 1번을 제외한 MST 구조를 구해야 함.

 

위의 4가지 경우를 전부 따져보면 어쨌든 1번을 제외한 최단거리를 구해하는 걸 알 수 있습니다.

문제 이해가 어렵지 구현 난이도는 일반적인 크루스 칼 알고리즘입니다.

 

 

2-2. 설계

 

3. 코드

import java.io.*;
import java.util.*;

public class Boj_2406_안정적인네트워크 {
	static int N, M, par[];
	static Queue<int[]> pq;
	public static void main(String[] args) throws IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(in.readLine());
		N = stoi(st.nextToken());
		M = stoi(st.nextToken());
		init();
		for (int i = 0; i < M; i++) {
			 st = new StringTokenizer(in.readLine());
			 int a = stoi(st.nextToken())-1;
			 int b = stoi(st.nextToken())-1;
			 union(a, b);
		}
		pq= new PriorityQueue<>((a,b)->(a[2]-b[2]));
		for(int i=0; i<N; i++) {
			st = new StringTokenizer(in.readLine());
			for(int j=0; j<N; j++) {
				int x = stoi(st.nextToken());
				if(i==0 || j==0 || i==j) {
					continue;
				}
				
				pq.add(new int[] {i, j, x});
			}
		}
		int cnt=0;
		int sum=0;
		List<int[]> list= new ArrayList<>();
		while(!pq.isEmpty()){
			int cur[] = pq.poll();
			if(find(cur[0]) != find(cur[1])) {
				sum+=cur[2];
				cnt++;
				union(cur[0], cur[1]);
				list.add(new int[] {cur[0],cur[1]});
			}
		}
		StringBuilder sb = new StringBuilder();
		sb.append(sum).append(" ").append(cnt).append("\n");
		for(int[] arr: list) {
			sb.append(arr[0]+1).append(" ").append(arr[1]+1).append("\n");
		}
		System.out.println(sb.toString());
	}

	static void union(int a, int b) {
		a = find(a);
		b = find(b);
		if (a > b) {
			par[b] = a;
		} else {
			par[a] = b;
		}
	}

	static int find(int x) {
		if (x == par[x]) {
			return x;
		}
		return par[x] = find(par[x]);
	}

	static void init() {
		par = new int[N];
		for (int i = 0; i < N; i++) {
			par[i] = i;
		}
	}

	static int stoi(String s) {
		return Integer.valueOf(s);
	}
}