[컴퓨팅 사고력] 네트워크 연결

원당이는 컴퓨터와 컴퓨터를 모두 연결하는 네트워크를 구축하려고 합니다.

하지만 아쉽게도 허브가 없어서 컴퓨터와 컴퓨터를 직접 연결해야 합니다.

그런데 모든 컴퓨터가 자료를 공유하기 위해서는 모든 컴퓨터가 연결되어 있어야 합니다.

이때 네트워크 연결 비용을 책정해야 되는데 기왕이면 가장 작은 금액으로 연결을 하고 싶습니다.

 

다음과 같이 컴퓨터와 컴퓨터의 연결하는 비용이 주어졌을때 최소로 모든 컴퓨터를 연결하는 비용은 얼마인지 구해 주세요.

 

6대의 컴퓨터가 있으며 연결비용은 다음과 같습니다.

컴퓨터번호,컴퓨터번호- 연결비용 

1,2 - 5

1,3 - 4

2,3 - 2

2,4 - 7

3,4 - 6

3,5 - 11

4,5 - 3

4,6 - 8

5,6 - 8

 

문제풀이)

그림으로 그려보면 위와 같습니다.

여기서 가장 작은 비용을 먼저 취하는 방법으로 연결을 해 주게 되면

2의 비용으로 2-3 을 연결하고

3의 비용으로 4-5를 연결하고

4의 비용으로 1-3을 연결하고

5의 비용으로 1-2를 연결하려고 보니 이미 1과 2는 통신이 가능하므로 연결하지 않고

6의 비용으로 3-4를 연결하고

7의 비용으로 2-4를 연결하려고 보니 이미 2와 4는 통신이 가능하므로 연결하지 않고

8의 비용으로 4-6 또는 5-6을 연결하면 모든 컴퓨터가 통신을 하게 됩니다.

따라서 2 + 3 + 4 + 6 +8 = 23 의 비용으로 연결이 됩니다.

 

컴퓨팅사고력

컴퓨팅 과학에서 네트워크에 많이 나타나는 전송경로에 관한 문제로 그래프로 나타내어 해결하는 방법에 관한 문제입니다.

이러한 문제를 컴퓨팅과학에서는 크루스칼 알고리즘이나 프림 알고리즘을 이용하여 최소비용을 찾게 되는데 위의 설명한 방법은 크루스칼 알고리즘에 해당합니다.

크루스칼 알고리즘은 비용을 오름차순으로 정렬한 후에 가장 작은 비용부터 네트워크를 연결하여 진행하면서 서로 같은 집합이 되는 경우에는 연결 하지 않고 서로 다른 집합인 경우에만 연결을 해 주는 방법으로 최소비용을 구해 줄 수 있습니다.

비슷한 방법으로 프림알고리즘이 있는데 프림 알고리즘은 먼저 한 정점을 선택 한 후에 정점에서 연결되는 간선중에서 가장 작은 비용을 선택한 후 그 간선을 연결 후에 모든 간선을 비교해서 그 중에서 가장 작은 간선으로 다음 정점을 연결하는 방법으로 해결하는 알고리즘입니다.

이러한 그래프 알고리즘은 통신이나 도로건설 또는 배관공사 등 다양한 실생활에서 사용되는 알고리즘입니다.