[20010] 악덕 영주 혜유 - Java[자바]

 

 

| 문제 링크

 

https://www.acmicpc.net/problem/20010

20010번: 악덕 영주 혜유

 

 

 

 

---

 

 

 

 

 

| 문제

 

1. 첫 줄에 마을의 수 N(1 ≤ N ≤ 1,000)과 설치 가능한 교역로의 수 K(1 ≤ K ≤ 1,000,000)가 주어집니다.
2. 두 번째 줄부터 K+1줄에는 서로 다른 두 마을의 번호 a, b (a ≠ b)와 두 마을을 연결하는 비용 c(1 ≤ c ≤ 1,000,000) 가 주어집니다.
3. 마을은 0번 부터 시작하며, 첫 번째 줄에 마을을 모두 연결하는 최소 비용을, 두 번째 줄에 마을과 마을을 이동하는 비용이 가장 큰 경로의 비용을 출력하시오.

 

 

 

---

 

 

 

 

| 풀이

 

마을을 최소 비용으로 모두 연결하는 MST와 MST에서 가장 긴 경로(트리의 지름)를 구하는 방식 두 가지로 나누어 푸는 문제입니다. MST는 Kruskal 알고리즘을 사용하였으며, 트리의 지름은 dfs를 두 번(임의의 노드에서 가장 먼 노드의 정보를 구하고, 가장 먼 노드로부터 다시 한 번 가장 먼 노드를 구함) 구해 문제를 풀었습니다.

 

 

1. N개의 노드는 초기에 자기 자신을 root(노드가 서로 연결되지 않았음을 뜻함)로 가지고 있습니다.
2. 간선의 정보를 가중치(비용)를 오름차순으로 우선순위 큐에 넣습니다.
3. 우선순위 큐를 하나씩 꺼내면서 두 노드의 root가 동일한 경우 이미 이어져있는 것으로 판단하고 continue, 동일하지 않다면 이이져있지 않는 것으로 판단해 연결해줍니다. (Kruskal 알고리즘)
4. 3번 동작을 통해 노드를 연결하며, MST의 비용과 MST의 인접리스트를 생성해 줍니다.
5. 4번에서 만든 MST 인접리스트를 활용해 0(임의의 노드)번 노드에서 dfs를 통해 가장 먼 노드의 위치를 구해줍니다.(가장 긴 간선의 끝 위치를 구함)
6. 5번에서 찾은 가장 먼 노드에서 dfs를 통해 다시 한 번 가장 먼 노드의 위치까지의 비용을 구해줍니다.

 

 

 

---

 

 

 

 

 

| 코드

 

import java.io.*;
import java.util.ArrayList;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.StringTokenizer;

class Node20010 implements Comparable<Node20010>{
	int from, to, w;

	public Node20010(int from, int to, int w) {
		this.from = from;
		this.to = to;
		this.w = w;
	}
	
	public Node20010(int to, int w) {
		this.to = to;
		this.w = w;
	}
	
	@Override
	public int compareTo(Node20010 o){
		return w-o.w;
	}
	
}

public class Main {
	
	public static int n, maxIdx;
	public static long max = 0;
	public static int[] parents;
	public static boolean[] flag;
	public static Queue<Node20010> pq = new PriorityQueue<>();
	public static List<Node20010>[] list;

	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringBuilder sb = new StringBuilder();
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		int n = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());
		
		//각 노드는 자기 자신을 뿌리로 시작함(각 노드가 연결되어있지 않음을 의미)
		parents = new int[n];
		for(int i = 0; i<n; i++)
			parents[i] = i;
		
		//MST의 정보가 들어갈 인접리스트 생성
		list = new ArrayList[n];
		for(int i = 0; i<n; i++)
			list[i] = new ArrayList<>();
		
		//간선들의 정보를 가중치 오름차순으로 pq에 넣음
		for(int i = 0; i<m; i++) {
			st = new StringTokenizer(br.readLine());
			int from = Integer.parseInt(st.nextToken());
			int to = Integer.parseInt(st.nextToken());
			int w = Integer.parseInt(st.nextToken());
			
			pq.add(new Node20010(from,to,w));
		}
		
		//MST 비용과 인접리스트 생성
		sb.append(kruskal()).append('\n');
		
		//임의의 노드(0에서 시작)로 부터 가장 먼 노드의 위치를 구함
		flag = new boolean[n+1];
		flag[0] = true;
		dfs(0,0);
		
		//maxIdx에 0번 노드로부터 가장 먼 노드의 위치가 저장되었기에 해당 노드로 부터 다시 한 번 dfs를 시행해 가장 긴 간선의 정보를 max에 넣음
		max = 0;
		flag = new boolean[n+1];
		flag[maxIdx] = true;
		dfs(maxIdx,0);
		
		sb.append(max);
		bw.write(sb.toString());
		br.close();
		bw.close();
		
	}
	
	//연결된 그래프의 뿌리 찾기
	public static int find(int node) {
		if(parents[node]==node)
			return node;
		return parents[node] = find(parents[node]);
	}
	
	//MST 비용과 인접리스트 구하기
	public static long kruskal() {
		//MST 비용 
		long cost = 0;
		//연결된 노드의 개수를 count해 n-1개와 동일해지면 break로 최적화
		int cnt = 0;
		while(!pq.isEmpty()) {
			Node20010 now = pq.poll();
			int from = now.from;
			int to = now.to;
			int w = now.w;
			
			int a = find(from);
			int b = find(to);
			if(a == b)
				continue;
			parents[a] = b;
			cost += (long) w;
			//MST 인접리스트 생성
			list[from].add(new Node20010(to,w));
			list[to].add(new Node20010(from,w));
			if(++cnt == n-1)
				break;
		}
		
		return cost;
	}
	
	//가장 긴(비용이 가장 비싼) 이어진 간선 찾기 
	public static void dfs(int s, long cost) {
		if(max<cost) {
			max = cost;
			maxIdx = s;
		}
		
		for(Node20010 next : list[s]) {
			int to = next.to;
			//방문한 곳이라면 continue(돌아가는 것을 방지)
			if(flag[to])
				continue;
			flag[to] = true;
			
			dfs(to,cost+next.w);
		}
	}

}