프로젝트 오일러 107번

 

 

 

The following undirected network consists of seven vertices and twelve edges with a total weight of \(243\).

 

The same network can be represented by the matrix below.

 

	A	B	C	D	E	F	G
A	-	16	12	21	-	-	-
B	16	-	-	17	20	-	-
C	12	-	-	28	-	31	-
D	21	17	28	-	18	19	23
E	-	20	-	18	-	-	11
F	-	-	31	19	-	-	27
G	-	-	-	23	11	27	-

 

However, it is possible to optimize the network by removing some edges and still ensure that all points on the network remain connected. The network which achieves the maximum saving is shown below. It has a weight of \(93\), representing a saving of \(243-93=150\) from the original network.

Using network.txt, a 6K text file containing a network with forty vertices, and given in matrix form, find the maximum saving which can be achieved by removing redundant edges whilst ensuring that the network remains connected.

 

---

 

위 첫번째 그림에서 보여지는 네트워크는 7개의 꼭짓점과 꼭짓점들을 연결하는 12개의 변으로 이루어져 있으며, 각 변들의 가중치의 총합은 243이다. 

똑같은 네트워크를 표로 나타내면 위의 두 번째 그림과 같다.

하지만 위의 세 번째 그림과 같이 몇 개의 변을 제거하게 되더라도 여전히 모든 꼭짓점들이 변으로 연결되어 있으며, 가중치의 총합을 최소로 하는 네트워크를 만드는 것이 가능하다. 세 번째 네트워크의 가중치의 총합은 93이므로 원래 네트워크에 비해서 \(243-93=150\) 의 가중치를 절약할 수 있다.

network.txt 파일에는 꼭짓점이 40개인 네트워크가 위 두 번째 그림과 같은 표의 형태로 표현되어 있다. 이 네트워크도 모든 꼭짓점들이 연결되어 있으면서 가중치의 합이 최소가 되도록 일부 변들을 제거한다면 가중치의 총합을 얼마나 절약할 수 있을까?

 

이 문제는 널리 알려진 minimum spanning tree(MST) 이다. 각 꼭지점을 연결하는 모서리들에 적힌 weight 의 합이 최소가 되도록 각 꼭지점을 빠짐없이 연결하는 문제이다. 이 문제를 풀기 위한 여러 가지 방법들이 있지만 여기서는 가장 이해하기 쉬운 방법 하나를 소개하기로 한다. 예제를 보면서 문제 풀이법을 익히는 것이 최고로 좋은 방법이므로 이런 저런 군더더기 없이 바로 예제 문제를 보기로 하겠다.

제일 먼저 해야할 일은 weight 를 작은 것 부터 큰 것 순으로, 즉 오름차순으로 정리를 하는 것이다. 

그리고 weight가 가장 작은 모서리부터 연결을 해 나간다. 이 때 연결된 모서리들의 집합을 Connected Edges(CE)라고 하자. 현재는 연결된 모서리가 없으므로 CE={ } 즉, 공집합이 된다. 또한 꼭짓점들의 집합을  Vertices(V) 라고 하자. 현재는 V={, , , , , , , } 가 될 것이다. 

 

	가장 먼저 weight가 1인 FG 모서리를 연결한다.   그리고 FG 모서리를 connected edges(CE)에 추가한다.  CE=  또한 연결된 꼭지점들을 한데 묶어서 하나의 집합으로 표현하면서  V를 업데이트 한다.  V={, , , , , , }
	다음으로 weight가 작은 CG 모서리를 연결한다.  CE= FG 가 연결된 상태에서 CG가 연결되면 꼭짓점 C, G, F가 모두 연결 되므로 집합 와 집합 를 합집합하여 V를 나타낸다.  V={, , , , , }
	다음으로 weight가 작은 BF 모서리를 연결한다.  CE=   V={, , , , }
	다음으로 weight가 작은 것은 3인데, AF 모서리와 DE 모서리가   모두 그렇다. 이럴땐 임의로 하나를 택하여 연결한다. 여기서는   AF 모서리를 연결하도록 하겠다.  CE=  V={, , , }
	다음으로는 DE 모서리를 연결한다. CE= V={, , }
	다음으로 weight 가 작은 것은 4 인데, DH 모서리와 EH 모서리가 모두 그렇다. 임의로 EH 모서리를 연결한다. CE= V={, }
	다음으로 weight가 작은 모서리는 DH 모서리이지만, DH 모서리를 연결할 경우, DEH가 loop 가 되어 minimal spanning tree 가 되지 않는다. 따라서 DH 를 제외하고 다음으로 weight 가 작은 DG 모서리를 연결한다.  CE=  V={} 8개의 꼭짓점을 weight의 합이 최소가 되도록 연결하면 연결된 모서리는 정확히 8-1=7 개가 된다. 또한 집합 V의 원소의 개수는 1개가 되는 것을 확인할 수 있다.  따라서 이 두 가지 정보 중 하나를 이용하여 minimum spanning tree의 종료 시점을 알 수 있다.

 

예제를 이해했다면, 107번 문제를 푸는 데도 큰 어려움이 없을 것이다. 

절약된 weight는 전체 weight 총합에서 CE에 들어있는 모서리들의 weight 총합을 빼 주면 알 수 있다.

 

위 예제에서 풀이법은 Kruskal's 알고리즘을 간단히 소개한 것이다.