2 분 소요

문제

n개의 집과 m개의 길로 이루어진 마을을 2개로 분리하려고 한다.

각 분리된 마을 안의 집들은 서로 연결되도록 분할해야한다.

분리하면서 분리된 두 마을 사이에 있는 길들은 필요가 없으니 없앨 수 있으며 ,

분리된 마을 안에서도 임의의 두 집 사이 경로가 항상 존재하게 되면서 길을 더 없앨 수 있다.

길을 없애고 남은 유지비 합의 최솟값은?


핵심 아이디어

크루스칼 알고리즘

전체 마을을 최소 비용으로 잇는 최소 비용신장트리를 구하고,

그중 가장 가중치가 큰 간선 하나를 없애 마을을 분리한다.

그렇게 분리된 각각의 마을은 최소 비용신장트리 형태를 띈다


코드 (Java)
package graph;

import java.util.*;

public class 도시분할계획 {
	
	public static int[] parent  = new int[100001]; 
	public static ArrayList<Edge> edges = new ArrayList<>() ; 
	public static int n, m ;
	public static int result = 0 ; 
	
	public static int find(int x) { // (int x , int[] parent) 
		if(x == parent[x]) return x ;
		return parent[x] = find(parent[x]) ;
		// 이부분 문제 : 담아놓고 반환하지 않음 
		// static이 아닌 그냥 전달받은 매개변수를 변화시키는 것 --> 실제로 호출해준 곳의 parent 배열엔 아무 영향 주지 x 
		// ㄴㄴ 전달할 때 배열(참조형)을 전달하기 때문에 그 매개변수를 갱신하면 자동으로 해당 주소의 배열이 변경됨 
 	}
	
	public static void union(int x, int y) {
		int x_root = find(x) ; 
		int y_root = find(y) ; 
		/* 
		if(x_root < y_root)
			parent[y] = x_root ; 
		else
			parent[x] = y_root ; 
		ㄴ 이렇게 하면 안되는 이유 : union연산은 각 집합의 '루트노드'의 '부모'를 다른쪽 루트노드로 설정해주는 것 
		=> 이렇게 하면 그냥 x,y의 부모가 루트노드로 됨 (해당 노드의 '이동'인셈) -->  
		*/
		if(x_root < y_root)
			parent[y_root] = x_root ; 
		else
			parent[x_root] = y_root ; 
	}
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in) ; 
		
		n = sc.nextInt() ; 
		m = sc.nextInt() ; 
		
		// 부모 테이블 초기화 
		for(int i = 1 ; i <= n ; i++) {
			parent[i] = i ; 
		}
		
		// 그래프 만들기 
		for(int i = 0 ; i < m ; i++) {
			int a = sc.nextInt() ;
			int b = sc.nextInt() ; 
			int c = sc.nextInt() ;
			edges.add(new Edge(c, a, b)) ;		
		}
		// 간선 가중치 오름차순 정렬 
		Collections.sort(edges);
		
		// 크루스칼 알고리즘 : 최소비용신장트리 만들기 
		int last = 0 ; 
		for(int i = 0 ; i < edges.size(); i++) { 
			// 마지막 간선은 더하지 않는다(분리) 
			// --> x : 얘는 분리가 아님, 마지막으로 검사한 간선이 꼭 사용되는 간선이라고 볼 수 없기 때문
			// => 최소신장비용트리를 먼저 만들고, 구성 간선 중 가장 큰 걸 빼줘야함
			int cost = edges.get(i).getDistance() ; 
			int nodeA = edges.get(i).getNodeA() ; 
			int nodeB = edges.get(i).getNodeB() ; 
			
			if(find(nodeA) != find(nodeB)) {
				union(nodeA, nodeB) ; 
				result += cost ; 
				last = cost ;  
			}
		}
		System.out.println(result-last);
	}
}


코드 (Python)
def find_parent(parent, x) : 
    if parent[x] != x :
        parent[x] = find_parent(parent, parent[x])
    return parent[x] 

def union_parent(parent, a, b):
    a = find_parent(parent, a) 
    b = find_parent(parent, b)

    if a < b : 
        parent[b] = a 
    else :
        parent[a] = b 

v, e = map(int, input().split())
parent = [0]*(v+1)

edges = [] 
result = 0 

for i in range(1, v+1) : 
    parent[i] = i 

for _ in range(e) : 
    a, b, cost = map(int, input().split())
    # 비용순으로 정렬하기 위해 튜플의 첫번째 원소를 비용으로 설정 
    edges.append((cost,a,b))

edges.sort()
last = 0 

for edge in edges : 
    cost, a, b = edge 

    if find_parent(parent, a) != find_parent(parent,b):
        union_parent(parent, a, b)
        result += cost 
        last = cost 
print(result-last)


댓글남기기