[백준] 유럽여행(1185) Java

문제 링크

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

1185번: 유럽여행

 

문제 요약

민식이는 여름에 유럽여행을 떠날 계획이다.

방문할 나라는 총 N개의 나라이고 편리하게 1번부터 N번까지 번호를 붙였다.

또한 이 나라들 사이에 이동 가능한 길은 M개가 있는데 민식이는 귀찮기 때문에 N개의 나라가 서로 연결된 것을 유지시키면서 최대한 많은 길을 지도에서 제거하고자 한다. 즉, N-1개의 길만을 남겨야할 것이다.

 

각 길을 통과하기 위한 비용이 각기 다르고 한 나라를 도착하면 내야할 비용 역시 나라마다 다르게 정해져있다.

민식이는 모든 도시를 최소 한번 이상 방문하면서 최소 비용이 드는 방법을 찾고 있다.

물론 길과 나라는 여러 번 방문할 수 있고, 첫 시작 나라는 민식이가 정할 수 있고, 마지막 나라는 시작 나라로 돌아와야만 한다. 

 

입력

첫 줄에는 방문할 나라의 수 N(5 ≤ N ≤ 10,000)과 이 나라들 사이를 연결하는 길의 수 P(N-1 ≤ P ≤ 100,000)가 주어진다.

두 번째 줄 부터 N+1번째 줄까지 i+1번째 줄에는 i번째 나라를 방문할 때 드는 비용 Ci (1 ≤ Ci ≤ 1,000)가 입력된다.

다음 P개의 줄에는 P개의 길에 대한 정보를 의미하는 세 정수 Sj, Ej, Lj가 입력되는데

이는 Sj번째 나라와 Ej번째 나라 사이를 연결짓는 길을 통과하기 위해서는 Lj 비용이 든다는 의미이다. (Sj ≠ Ej, 0 ≤ Lj ≤ 1,000)

 

출력

민식이가 유럽여행을 마치기 위한 최소비용을 출력한다.

 

접근법

N - 1개의 길만 남기고 전부 지운다는 점과 최소 비용을 구해야 한다는 점에서 MST와 관련된 문제임을 쉽게 알 수 있다.

 

문제는 edge(길)에만 cost가 있는 것이 아니라 node에도 cost가 있다는 것.

즉 단순히 edge만 가지고 kruskal이나 prim 알고리즘을 적용해서 MST를 구하는 것으로는 문제를 풀 수 없다는 것이다.

 

하지만 MST의 특징을 잘 안다면 이 문제를 쉽게 풀 수 있다. MST에 대해 잘 모른다면 여기를 참고하시라.

이 문제를 해결하기 위한 핵심 요소 3가지는 다음과 같다.

1. N - 1개의 길만 남기고 전부 지운다. 즉 cycle이 없는 spanning tree의 형태가 된다.
2. 최소 비용을 구해야한다. 이를 위해서 spanning tree중 cost의 합이 최소인 MST(Minimum Spanning Tree)를 찾아야 한다.
3. 모든 나라를 전부 방문한 뒤 시작 지점으로 다시 돌아와야한다.

1번과 2번은 MST와 직접적으로 연관된 부분이기 때문에 핵심 요소라는 것을 쉽게 받아들일 수 있는데, 3번은 왜 핵심 요소일까?

바로 MST에서는 모든 node를 순회하고 시작 지점으로 다시 돌아오기 위해서는, cycle이 없다는 MST의 특징에 의해 모든 edge를 정확히 2번 거쳐가야 하기 때문이다.

Cycle이 없다는 것은 두 node 사이의 최단 경로(여기서는 cost와 관계 없이 path를 이루는 edge의 개수가 가장 적은 경로를 의미한다)가 unique 하다는 것을 의미한다.

Spanning tree 예시

예를 들어 위와 같이 cycle이 없는 spanning tree에서 node1 과 node5 사이의 최단 경로는 1 - 2 - 3 - 5로 유일하다.

반대로 말하면 node5와 node1 사이의 최단 경로는 5 - 3 - 2 - 1 로 유일하다는 것이다.

즉 node1에서 출발해서 node5까지 갔다가 다시 node1로 돌아오는 최단 경로는 1 - 2 - 3 - 5 - 3 - 2 - 1 하나 밖에 존재하지 않는다는 것을 의미한다.

 

그리고 여기서 알 수 있는 또 다른 중요한 사실 하나는, 경로 1 - 2 - 3 - 5 - 3 - 2 - 1  를 edge의 관점에서 바라보면

edge 1 - 2 와 edge 2 - 1, edge 2 - 3 과 edge 3 - 2, edge 3 - 5 와 edge 5 - 3

이렇게 경로 안에 존재하는 edge를 정확히 2번씩 거쳐갔다는 것이다(양방향 edge이기 때문에 1 - 2와 2 - 1은 동일하다).

 

즉 우리가 구해야 할 답인 최소 여행 비용은 MST의 모든 edge의 cost의 합의 2배에 각 나라를 거쳐간 비용을 더해주면 된다는 것을 알 수 있다.

 

그런데 지금까지는 edge의 cost만 고려했지 각 나라의 여행 비용은 고려하지 않았다. 그리고 이 부분에서 열받는 점은

Spanning tree 예시

이런 spanning tree에서 node2에서 출발해 모든 node를 순회하고 다시 node2로 돌아오려면, 각 edge는 정확히 2번씩만 방문하면 되지만 각 node의 방문 횟수는 그래프의 형태에 따라 달라진다는 것을 쉽게 알 수 있다.

위 그래프에서 node2의 방문 횟수는 출발을 포함해서 5번이나 되지만, 나머지 node는 1번씩만 방문하게 된다 (경로 2 - 1 - 2 - 4 - 2 - 5 - 2 - 3 - 2)

 

하지만 다행히도 우리는 node의 방문 횟수는 모르지만, edge의 방문 횟수가 2번이라는 것을 알고 있다.

Edge를 방문한다는 것은(거쳐간다는 것은) edge의 양 끝 node 역시 1 번씩 방문한다는 것을 의미한다. 이를 이용해서 각 edge의 cost에 양 끝 node의 cost를 각각 더해주기만 하면, 더 이상 각 node를 몇 번 방문하는지 생각을 할 필요가 없이 edge의 관점에서만 이 문제를 해결할 수 있게 된다.

 

정확히는 edge를 2번 방문하기 때문에 각 edge의 cost에 2를 곱하고 거기에 양 node의 cost를 더해주면 된다.

Spanning tree 예시

위의 예시에서 node2에서 출발해서 모든 node를 순회하고 다시 돌아오는 경로 2 - 1 - 2 - 4 - 2 - 5 - 2 - 3 - 2 를 다시 살펴보자.

일단 node2에서 node1을 방문하고 다시 node2로 돌아오는 경로 2 - 1 - 2를 살펴보면 edge가 양방향이기 때문에 2 - 1 과 1 - 2의 cost가 동일하다. 이 부분이 edge의 cost에 2를 곱하는 부분에 해당한다.

 

그리고 node2와 node1을 방문했기 때문에 양 node의 cost를 각각 더해줘야 하는데, 여기서 이상한 점은 경로 2 - 1 - 2 에서 node2는 두 번 방문했다는 것이다. 이는 node2가 출발지라서 1번 더 방문하게 되기 때문에 일어나는 경우이다. 즉 이 것은 특수한 경우이기 때문에 일단 고려하지 않고, 마지막 정답에 출발지인 node2의 cost를 더해주기만 하면 해결된다.

다시 말하면 경로 2 - 1 - 2 - 4 - 2 - 5 - 2 - 3 - 2 를 마치 출발지가 존재하지 않는 경로 x - 1 - 2 - 4 - 2 - 5 - 2 - 3 - 2 이렇게 생각하고 cost를 계산한 뒤 마지막 최소 비용에 출발지인 node2의 cost를 더해주면 된다는 것이다.

 

따라서 경로 2 - 1 - 2 는 x - 1 - 2 가 되고, edge를 두번 방문하고 양 끝의 node를 각각 한 번씩 방문한 것이 되기 때문에 edge의 cost에 2를 곱하고 양 node의 cost를 더해주면 문제를 해결할 수 있다는 것을 알 수 있다.

2 - 1 - 2 뒤의 나머지 경로도 마찬가지로 edge를 두 번 방문하고 양 node를 한 번씩 방문하게 된다는 것을 알 수 있다.

 

결국 설명이 길었지만 이 문제를 해결하기 위해서는

1. Edge를 입력 받을 때 edge의 cost를 edge의 cost에 2를 곱한 값에 edge의 양 끝 node의 cost를 더해준 값으로 설정한 뒤 PriorityQueue에 넣는다.
2. Kruskal 알고리즘을 적용해서 MST를 구한다.
3. Kruskal로 구한 MST에서 edge의 cost의 총합을 구한 뒤, 출발지의 cost를 한 번 더해준다. 이 때 출발지는 추가적으로 1번 더 방문하게 되는 node이므로 가장 비용이 적은 node를 출발지로 정하면 된다.

이렇게 3가지 단계만 거치면 된다.

 

실제 코드로 보면 kruskal 알고리즘으로 MST를 구하는 코드와 다른 부분이 거의 없다. 일반적인 MST를 구하는 코드에 Edge를 입력받을 때 cost에 대한 약간의 수식을 추가하고, 마지막에 정답에 cost를 더해주는 것을 추가하기만 하면 이 문제를 풀 수 있다.

 

시간 복잡도

Kruskal 알고리즘에 약간의 양념을 친 경우이므로 시간 복잡도는 kruskal과 동일한 O(ElogE) (이 문제에선 O(PlogP)) 이다.

P가 10만 이하이고 시간 제한이 2초이므로 충분하다.

 

 

공간 복잡도

여행지의 비용을 저장하기 위한 int[N] 배열 => 최대 4 * 10,000 byte = 약 40KB

3개의 int 멤버 변수를 갖고 있는 P 크기의 PriorityQueue<Edge> => 최대 3 * 4 * 100,000 byte = 약 1.2MB

Disjoint set을 위한 int[N] 배열 => 최대 4 * 10,000 byte = 약 40KB

 

약 2MB 선에서 정리 되는 듯 싶다.

 

풀면서 놓쳤던 점

딱히 없었다.

 

 

이 문제에서 얻어갈 점

Kruskal 알고리즘

Spanning tree의 특징

 

 

코드

import java.util.*;
import java.io.*;

class Main
{
	public static void main(String[] args) throws Exception
	{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;

		int N, P;
		st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		P = Integer.parseInt(st.nextToken());

		int[] countryCost = new int[N + 1];
		int minCountryCost = Integer.MAX_VALUE;
		for (int i = 1; i <= N; i++)
		{
			countryCost[i] = Integer.parseInt((new StringTokenizer(br.readLine())).nextToken());
			minCountryCost = Math.min(minCountryCost, countryCost[i]);
		}

		PriorityQueue<Edge> edges = new PriorityQueue<Edge>(P);

		int node1, node2, cost;
		for (int i = 0; i < P; i++)
		{
			st = new StringTokenizer(br.readLine());
			node1 = Integer.parseInt(st.nextToken());
			node2 = Integer.parseInt(st.nextToken());
			cost = Integer.parseInt(st.nextToken());

			cost = cost * 2 + countryCost[node1] + countryCost[node2];
			edges.add(new Edge(node1, node2, cost));
		}

		DisjointSet ds = new DisjointSet(N);

		long tripCost = 0;
		int cnt = 0;
		Edge e;
		while (!edges.isEmpty() && cnt < N - 1)
		{
			e = edges.poll();

			if (ds.find(e.node1) != ds.find(e.node2))
			{
				ds.union(e.node1, e.node2);
				tripCost += e.cost;
				cnt++;
			}
		}

		System.out.println(tripCost + minCountryCost);
	}
}

class Edge implements Comparable<Edge>
{
	int node1;
	int node2;
	int cost;

	public Edge(int node1, int node2, int cost)
	{
		this.node1 = node1;
		this.node2 = node2;
		this.cost = cost;
	}

	public int compareTo(Edge other)
	{
		if (this.cost > other.cost)
			return (1);
		else if (this.cost == other.cost)
			return (0);
		else
			return (-1);
	}
}

class DisjointSet
{
	int parent[];

	public DisjointSet(int N)
	{
		parent = new int[N + 1];
		for (int i = 1; i <= N; i++)
			parent[i] = i;
	}

	public int find(int e)
	{
		if (parent[e] == e)
			return (e);
		parent[e] = find(parent[e]);
		return (parent[e]);
	}

	public void union(int e1, int e2)
	{
		int par1 = find(e1);
		int par2 = find(e2);
		parent[par1] = par2;
	}
}