[백준 1185번] 유럽여행 (java)

1185번: 유럽여행

 

전체 나라 개수가 N개이고, 이어져 있는 길이 N-1개 일 때,

최소 비용으로 어느 시작 나라 하나를 정해서 모든 나라를 다 방문한 후 다시 시작 나라로 돌아오기 위해서는 나라는 2*N-1개를 방문하고, 길은 2*(N-1)번을 지나야 한다.

 

따라서, 각 길의 비용은 이어져 있는 두 나라의 비용 + 길의 비용*2 로 정하면 된다.

예를 들어, 1번과 2번 나라 사이의 길의 비용은

1번 나라의 비용(10) + 2번 나라의 비용(10) + 원래 길의 비용(5)*2 = 30 이 된다.

 

 

 

그 다음, 새로 구한 간선의 가중치를 이용하여 최소 신장 트리(MST)를 구한다.

본인은 이번 문제에서 프림(Prim) 알고리즘을 이용하여 최소 신장 트리를 구하였다.(프림 알고리즘의 경우, 아래 포스팅을 참고)

https://lotuslee.tistory.com/46?category=973233 

MST(Minimum Spanning Tree) - 1. 프림 알고리즘

 

최소 신장 트리를 구한 결과는 아래 그림과 같다.

 

최소 신장 트리의 모든 간선의 합을 구하면 30 + 40 + 40 + 60 = 170 이다.

여기서 시작 나라의 비용을 더해줘야 한다.

최소비용을 유지하기 위해서는 5개의 나라들 중에서 비용이 가장 적은 나라를 시작 나라로 정해야 한다.

예제에서 가장 비용이 적은 나라는 5번 나라이다. (비용 = 6)

따라서 최종적으로 드는 최소 비용은 170 + 6 = 176 이 된다.

 

 

정답 코드 : 

	import java.io.*;
	import java.util.*;
	public class n01185 {
	static int N, P;
	static int[] cost;
	static boolean[] visited;
	static List<Pair>[] w;
	static int min = Integer.MAX_VALUE;
	public static void main(String[] args) throws Exception {
	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
	String[] input = br.readLine().split(" ");
	N = Integer.parseInt(input[0]);
	P = Integer.parseInt(input[1]);
	cost = new int[N + 1];
	visited = new boolean[N + 1];
	w = new ArrayList[N + 1];
	for (int i = 0; i <= N; i++) {
	w[i] = new ArrayList<>();
	}
	for (int i = 1; i <= N; i++) {
	cost[i] = Integer.parseInt(br.readLine());
	min = Math.min(min, cost[i]);
	}
	for (int i = 0; i < P; i++) {
	input = br.readLine().split(" ");
	int S = Integer.parseInt(input[0]);
	int E = Integer.parseInt(input[1]);
	int L = Integer.parseInt(input[2]);
	w[S].add(new Pair(E, cost[S] + cost[E] + 2 * L));
	w[E].add(new Pair(S, cost[S] + cost[E] + 2 * L));
	}
	long res = getMST() + min;
	bw.write(res + "\n");
	bw.flush();
	}
	public static long getMST() {
	long sum = 0;
	PriorityQueue<Pair> pq = new PriorityQueue<>();
	pq.offer(new Pair(1, 0));
	while (!pq.isEmpty()) {
	Pair pair = pq.poll();
	if (visited[pair.n])
	continue;
	visited[pair.n] = true;
	sum += pair.w;
	for (Pair np : w[pair.n]) {
	if (!visited[np.n]) {
	pq.offer(np);
	}
	}
	}
	return sum;
	}
	static class Pair implements Comparable<Pair> {
	int n, w;
	Pair(int n, int w) {
	this.n = n;
	this.w = w;
	}
	@Override
	public int compareTo(Pair o) {
	return w - o.w;
	}
	}
	}

view raw 1185.java hosted with ❤ by GitHub