섹션 3. 코딩테스트 [실전편] - 08. 그래프 - (6) 최소 비용 신장 트리

⬛ 08-7. 최소 신장 트리

🟦 신장 트리

• n개 정점. 무방향 그래프에서 (사이클 없이) 간선 n-1 개로 이루어진 부분 그래프

🟦 최소 비용 신장 트리

• 정점 n개, 간선 n-1개. 사이클 X . 연결 그래프인 신장 트리의 조건을 만족하면서 총 간선의 가중치의 합이 최소인 트리
• 그래프의 모든 노드들을 연결하는 부분 그래프 중 가중치 합이 최소인 트리를 의미

🟧 1) 크루스칼 알고리즘 - (I)

• 가중치 ‘높은’ 간선 제거하여 최소비용 만듬
• (1) 그래프의 모든 간선들 가중치 내림차순 정렬
• (2) 사이클 X, 단절 X 가장 큰 간선 제거
• (3) 간선 n-1개 남을 때까지 반복 후 종료

🟧 1) 크루스칼 알고리즘 - (II)

• 가중치 ‘낮은’ 간선 삽입하며 최소비용 만듬
• (1) 그래프의 모든 간선들 가중치 오름차순 정렬
• (2) 사이클X. 단절X 가장 낮은 간선 삽입
• (3) 간선 n-1개 남을 때까지 반복 후 종료

🟧 2) 프림 알고리즘

• (간선 정렬없이) 하나의 정점에서 시작하여 트리를 확장해나감
• 확장 정점들에 부속된 모든 간선들 비교하며 가장 낮은 간선을 확장시킨다.
• (1) 시작 정점 선택
• (2) 선택 정점에 부속된 모든 간선들 중 (사이클X, 단절X)가장 가중치 낮은 간선 연결
• (3) 간선 n-1개 남을 때까지 반복 후 종료

⬛ 최소 비용 신장 트리의 핵심 이론

1) 에지 리스트로 그래프를 구현하고 유니온 파인드 배열 초기화하기

• 최소신장 트리는 데이터를 ‘Edge’ 중심으로 저장하므로 에지 리스트의 형태로 데이터를 저장해야 한다.
• 또한, 사이클 처리를 위해 유니온 파인드도 함께 구현

2) 그래프 데이터를 ‘가중치 기준’ 정렬하기

3) 가중치가 낮은 엣지부터 차례대로 연결 시도

• 단, 해당 간선 연결 시, 사이클 형성 유무를 find 연산을 통해 확인한 후 union연산을 통해 두 노드를 연결해야 한다.

4) 위의 과정을 간선 n-1개 될 때까지 반복한다.

5) 총 에지 비용 출력

---

🟦 백준 1197번. 최소 신장 트리 구하기

문제

그래프가 주어졌을 때, 그 그래프의 최소 스패닝 트리를 구하는 프로그램을 작성하시오.

최소 스패닝 트리는, 주어진 그래프의 모든 정점들을 연결하는 부분 그래프 중에서 그 가중치의 합이 최소인 트리를 말한다.

입력

첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 가중치 C인 간선으로 연결되어 있다는 의미이다. C는 음수일 수도 있으며, 절댓값이 1,000,000을 넘지 않는다.

그래프의 정점은 1번부터 V번까지 번호가 매겨져 있고, 임의의 두 정점 사이에 경로가 있다. 최소 스패닝 트리의 가중치가 -2,147,483,648보다 크거나 같고, 2,147,483,647보다 작거나 같은 데이터만 입력으로 주어진다.

출력

첫째 줄에 최소 스패닝 트리의 가중치를 출력한다.

풀이 - 최소비용트리

• 우선순위 큐를 사용하여 Edge 의 가중치가 자동 오름차순 정렬되도록 담아두고, while문이 사용한 간선 개수 N-1 될 때까지 반복하게 만들기
• 뽑은 현재 엣지의 s, e의 부모fin() 했을 때 부모가 다른 경우에만 union연산으로 두 정점을 연결한다.
• 최소비용 += 연결한 가중치 val 누적합
• 사용한 간선++ 처리

import java.util.PriorityQueue;
import java.util.Scanner;

/*1197번. 최소 스패닝 트리 - 최소비용신장트리 */
class Edge implements Comparable<Edge>{
	int s; 
	int e;
	int val;
	Edge(int s, int e, int val){
		this.s = s;
		this.e = e;
		this.val = val;
	}
	@Override
	public int compareTo(Edge o) {
		// TODO Auto-generated method stub
		return this.val - o.val;//가중치 값 기준 오름차순 정렬되도록 
	}
}

public class Main {
	static int V, E;
	static int[] parent;//유니온 파인드 위해 
	//find
	static int find(int v) {
		if(v == parent[v]) return v;
		else {
			return parent[v] = find(parent[v]);//계속 재귀로 부모==자기 자신 될 때까지 호출 
		}
	}
	
	//union
	static void union(int a, int b) {
		a = find(a);
		b = find(b);
		if(a!= b) {
			parent[b] = a;//부모를 a로 세팅 
		}
	}
	
	
	//실행 메인 
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner kb = new Scanner(System.in);
		V = kb.nextInt();
		E = kb.nextInt();
		PriorityQueue<Edge> pQ = new PriorityQueue<>();
		
		parent = new int[V+1];
		//초기화
		for(int i=1; i<=V; i++) {
			parent[i] = i;//자기 자신으로 부모 초기화 
		}
		
		for(int i=0; i<E; i++) {
			int a = kb.nextInt();
			int b = kb.nextInt();
			int v = kb.nextInt();
			pQ.add(new Edge(a, b, v));//자동 오름차순 정렬
		}
		//최소비용 신장 트리 알고리즘
		//오름차순 정렬된 가중치 순서대로 연결할 건데 만약 사이클 형성 하면 X
		int useEdgeNum = 0;
		int answer = 0;// 가중치 합 누적용 
		while(useEdgeNum < V-1) { //사용한 간선의 개수 N-1까지
			Edge cur = pQ.poll();//현재 가장 낮은 간선 뽑기
			if(find(cur.s) != find(cur.e)) { // 두 정점의 부모가 같지 않은 경우에만 (사이클X)
				union(cur.s, cur.e);//둘이 연결
				answer += cur.val;//연결한 비용 누적 
				useEdgeNum++;//간선 개수 ++
			}
		}	
		//정답 출력 
		System.out.println(answer);
	}
}

---

🟦 백준 1414번. 불우이웃 돕기

문제

다솜이는 불우이웃 돕기 활동을 하기 위해 무엇을 할지 생각했다. 마침 집에 엄청나게 많은 랜선이 있다는 것을 깨달았다. 마침 랜선이 이렇게 많이 필요 없다고 느낀 다솜이는 랜선을 지역사회에 봉사하기로 했다.

다솜이의 집에는 N개의 방이 있다. 각각의 방에는 모두 한 개의 컴퓨터가 있다. 각각의 컴퓨터는 랜선으로 연결되어 있다. 어떤 컴퓨터 A와 컴퓨터 B가 있을 때, A와 B가 서로 랜선으로 연결되어 있거나, 또 다른 컴퓨터를 통해서 연결이 되어있으면 서로 통신을 할 수 있다.

다솜이는 집 안에 있는 N개의 컴퓨터를 모두 서로 연결되게 하고 싶다.

N개의 컴퓨터가 서로 연결되어 있는 랜선의 길이가 주어질 때, 다솜이가 기부할 수 있는 랜선의 길이의 최댓값을 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 컴퓨터의 개수 N이 주어진다. 둘째 줄부터 랜선의 길이가 주어진다. i번째 줄의 j번째 문자가 0인 경우는 컴퓨터 i와 컴퓨터 j를 연결하는 랜선이 없음을 의미한다. 그 외의 경우는 랜선의 길이를 의미한다. 랜선의 길이는 a부터 z는 1부터 26을 나타내고, A부터 Z는 27부터 52를 나타낸다. N은 50보다 작거나 같은 자연수이다.

출력

첫째 줄에 다솜이가 기부할 수 있는 랜선의 길이의 최댓값을 출력한다. 만약, 모든 컴퓨터가 연결되어 있지 않으면 -1을 출력한다.

풀이

• 이 문제는 문자열 형태로 들어온 인접 행렬을 소문자, 대문자 별로 숫자 형태로 바꾼 뒤 i≠j 인 값에 대해서만 엣지 리스트에 담아 정렬하는 방식으로 최소비용을 만드는 것이 핵심이다.
• 총 랜선 비용합을 구한 뒤 최소 비용을 빼면, 다솜이가 기부할 수 있는 랜선 길이의 최대값이 나온다.

package to_0707_1;

/*백준 1414번. 불우이웃 돕기 */
import java.io.*;
import java.util.*;

public class Main {
	static int[] parent;
	static int N, sum;
	static PriorityQueue<lEdge> queue;
	//실행 메인 
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		queue = new PriorityQueue<>();
		//N개의 입력을 받을 건데 
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			char[] tempc = st.nextToken().toCharArray();
			//각 문자로 바뀐 j번째 값에 대하여 숫자 형태로 바꿔줄 거임 
			for (int j = 0; j < N; j++) {
				int temp = 0;
				//소문자일 경우 
				if (tempc[j] >= 'a' && tempc[j] <= 'z')
					temp = tempc[j] - 'a' + 1;
				//대문자일 경우
				else if (tempc[j] >= 'A' && tempc[j] <= 'Z')
					temp = tempc[j] - 'A' + 27;
				
				//총 랜선 길이 누적합 
				sum = sum + temp; // 총 랜선의 길의 저장
				//i!=j : 다른 컴터끼리만 연결한대쓰니까. 그리고 가중치 0이아니어야 존재하는 랜선이기 때문 
				if (i != j && temp != 0)
					queue.add(new lEdge(i, j, temp)); //큐에 Edge 형태로 담기 
			}
		}
		//결합 상태를 위해 부모 배열 생성 
		parent = new int[N];
		//자기 자신을 저장 
		for (int i = 0; i < parent.length; i++)
			parent[i] = i;
		//-> 최소비용 신장트리 알고리즘 수행 
		int useEdge = 0; //사용된 간선 카운팅 - N-1까지
		int result = 0; //최소비용 가중치 누적용 
		//큐가 비지 않을 때까지 반복 
		while (!queue.isEmpty()) { // 최소 신장 트리 알고리즘을 수행하여 줍니다.
			lEdge now = queue.poll();
			if (find(now.s) != find(now.e)) { // 같은 부모가 아니라면 -> 연결 가능
				union(now.s, now.e);
				result = result + now.v;
				useEdge++;
			}
		}
		//큐 비어서 빠져나온 상태가 간선 N-1개만 사용했으면 : 최대값 = 전체 - 최소비용 
		if (useEdge == N - 1)
			System.out.println(sum - result);
		else //그 외의 간선 사용하면 연결 못한 것이므로 -1 출력 
			System.out.println(-1);
	}
	//유니온 
	public static void union(int a, int b) { // union 연산 : 대표 노드끼리 연결하여 줌
		a = find(a);
		b = find(b);
		if (a != b)
			parent[b] = a;
	}
	//find
	public static int find(int a) { // find 연산
		if (a == parent[a])
			return a;
		else
			return parent[a] = find(parent[a]); // 재귀함수의 형태로 구현 -> 경로 압축 부분
	}
}
//Edge 클래스 
class lEdge implements Comparable<lEdge> {
	int s, e, v;

	lEdge(int s, int e, int v) {
		this.s = s;
		this.e = e;
		this.v = v;
	}
	@Override
	public int compareTo(lEdge o) {
		return this.v - o.v;
	}
}