백준 20010 <악덕 영주 혜유>

최소 스패닝 트리를 찾고 그 지점에서 가장 긴 거리의 합을 계산하는 문제이다.

 

문제 풀이

 

1. 0번 마을부터 시작해서 프림 알고리즘을 구성하면서 연결된 지점을 새로운 arraylist에 넣어준다.
2. 0번 마을에서부터 dfs를 하면서 가장 길게 이어진 합을 갱신해준다.

최소 스패닝을 구하게 되면 그림과 같이 빨간색 선들로 이뤄진 길이가 된다.

 

그중 가장 긴 길이는 0번 집에서 6번 집까지의 거리를 구하는 것이다.

 

즉 dfs를 하면서 가장 긴 길이를 매번 update 해주는 것이다.

 

연결되어 있는 집들과 그사이의 거리를 담을 div 클래스를 생성한다.

최소 스패닝 트리를 구성하기위해 kruskal 또는 prim 알고리즘을 사용하면 되는데 나는 여기서 prim알고리즘을 사용했다.

 

마을과 마을 중 가장 먼 거리를 구하기 위해 dfs를 사용했다.

 

전체 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {

	public static class div implements Comparable<div>{
		int now;
		int ne;
		int d;
		public div(int now,int ne, int d) {
			super();
			this.now=now;
			this.ne = ne;
			this.d = d;
		}
		@Override
		public int compareTo(div o) {
			// TODO Auto-generated method stub
			return this.d-o.d;
		}
	}
	static ArrayList<div> num[],bridge[];
	static boolean visit2[];
	static int n,k,sum,maxresult;
	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		BufferedReader br=new BufferedReader(new InputStreamReader (System.in));
		StringTokenizer st=new StringTokenizer(br.readLine());
		n=Integer.parseInt(st.nextToken());
		k=Integer.parseInt(st.nextToken());
		num=new ArrayList[n];
		bridge=new ArrayList[n];
		visit2=new boolean[n];
		for(int i =0;i<n;i++) {
			num[i]=new ArrayList<div>();
			bridge[i]=new ArrayList<div>();
		}
		for(int i=0;i<k;i++) {
			st=new StringTokenizer(br.readLine());
			int f=Integer.parseInt(st.nextToken());
			int s=Integer.parseInt(st.nextToken());
			int d=Integer.parseInt(st.nextToken());
			num[f].add(new div(f,s,d));
			num[s].add(new div(s,f,d));
		}
		find();//최단거리 발견
		visit2[0]=true;
		find2(0);
		System.out.println(sum);
		System.out.println(maxresult);
	}
	private static int find2(int next) {
		// TODO Auto-generated method stub
		ArrayList<Integer> max=new ArrayList<Integer>();
		int sum2=0;
		for(int i=0;i<bridge[next].size();i++) {
			if(visit2[bridge[next].get(i).ne]) {
				continue;
			}
			visit2[bridge[next].get(i).ne]=true;
			max.add(find2(bridge[next].get(i).ne)+bridge[next].get(i).d);
		}
		if(max.size()==0) {
			return 0;
		}
		Collections.sort(max);
		sum2+=max.get(max.size()-1);
		if(max.size()>=2) {
			sum2+=max.get(max.size()-2);
		}
		maxresult=Math.max(maxresult, sum2);
		return max.get(max.size()-1);
		
	}
	private static void find() {
		// TODO Auto-generated method stub
		PriorityQueue<div> pq=new PriorityQueue<div>();
		boolean visit[]=new boolean[n];
		for(int i=0;i<num[0].size();i++) {
			pq.add(num[0].get(i));
		}
		visit[0]=true;
		while(!pq.isEmpty()) {
			div next=pq.remove();
			if(visit[next.ne])
				continue;
			sum+=next.d;
			visit[next.ne]=true;
			bridge[next.ne].add(new div(next.ne,next.now,next.d));
			bridge[next.now].add(new div(next.now,next.ne,next.d));
			for(int i=0;i<num[next.ne].size();i++) {
				div next2=num[next.ne].get(i);
				if(visit[next2.ne]) {
					continue;
				}
				pq.add(next2);
			}
		}	
	}
}