[백준][BOJ2406] 안정적인 네트워크

1. 문제 : https://www.acmicpc.net/problem/2406

2406번: 안정적인 네트워크

---

2. 풀이 : Kruskal

---

3. 시간복잡도 : O(ElogE)

---

4. 설명

문제의 예제는 그림[1]과 같이 표현이 된다. 문제의 조건에서 본사 컴퓨터(1번)는 각 지사의 컴퓨터와연결되어 있는 네트워크를 보유하고 있다. 2번과 3번, 3번과 4번 컴퓨터는 직접 연결되어 있다.

그림[1]

문제에서 네트워크에 고장이 발생하는 경우는 다음과 같다.

    1) 직접 연결되어 있는 두 컴퓨터의 연결이 끊어지는 경우

    2) 컴퓨터가 고장 나는 경우

회사는 위와같이 고장이 발생하는 경우에도 모든 컴퓨터가 네트워크에 연결이 되어있길 원한다.

 

1번의 경우와 같이 직접 연결되어 있는 두 컴퓨터의 연결이 끊어지는 경우는 다음과 같다.

1-A. 본사의 컴퓨터와 지사의 컴퓨터의 네트워크가 끊어지는 경우

그림[2]

1번 컴퓨터와 2번 컴퓨터의 네트워크가 끊어지는 경우는 그림[2]와 같으며, 2번 컴퓨터와 3번 컴퓨터가 직접 연결되어 있으므로, 1번 컴퓨터와 2번 컴퓨터는 3번 컴퓨터를 통하여 연결이 되어 있다.

그림[3]

1번 컴퓨터와 5번 컴퓨터의 네트워크가 끊어지는 경우는 그림[3]과 같으며, 5번 컴퓨터는 다른 지사 컴퓨터와의 네트워크가 존재하지 않으므로 안정적인 네트워크 조건이 성립되지 않는다. 

즉, 본사 컴퓨터와의 네트워크가 끊기는 것을 대비하여 각 지사 컴퓨터들은 서로 네트워크가 형성되어 있어야 한다.

 

1-B. 지사간에 직접 연결된 컴퓨터들의 네트워크가 끊어지는 경우

그림[4]

3번 컴퓨터와 4번 컴퓨터의 네트워크가 끊어지는 경우는 그림[4]와 같으며, 모든 지사 컴퓨터들은 본사 컴퓨터와 직접 연결되어 있으므로 본사 컴퓨터를 통하여 네트워크가 형성된다.

임의의 지사 컴퓨터들간의 네트워크가 끊어지는 경우에도 본사 컴퓨터를 통하여 안정적인 네트워크가 형성이 된다.

 

2번의 경우와 같이 컴퓨터가 고장나는 경우는 다음과 같다.

2-A. 본사 컴퓨터가 고장나는 경우

그림[5]

본사 컴퓨터가 고장나는 경우는 그림[5]와 같으며, 5번 컴퓨터는 본사 컴퓨터와의 연결이 끊어짐으로인해 네트워크가 존재하지 않으므로 안정적인 네트워크 조건이 성립하지 않는다.

즉, 이와 같이 본사 컴퓨터가 고장이 나는 것을 대비하여 각 지사 컴퓨터들은 서로 네트워크가 형성되어 있어야 한다.

2- B. 지사 컴퓨터가 고장나는 경우

그림[6]

지사 컴퓨터인 3번 컴퓨터가 고장나는 경우는 그림[6]과 같으며, 모든 지사 컴퓨터들은 본사 컴퓨터와 직접 연결되어 있으므로 본사 컴퓨터를 통하여 네트워크가 형성된다.

임의의 지사 컴퓨터가 고장나는 경우에도 본사 컴퓨터를 통하여 안정적인 네트워크가 형성이 된다.

 

따라서, 고려할 대상은 1-A, 2-A 2가지 경우이며, 이를 대비하기위한 방법으로 각 지사간에 네트워크가 형성되어 있어야 한다.

안정적인 네트워크를 최소 비용으로 형성하기 위해서는 직접 연결된 지사 컴퓨터 네트워크를 제외하고, 나머지 지사 컴퓨터간의 네트워크를 최소 비용으로 연결하여 MST를 형성한다.

그림[7]

그림[7]과 같이 4번 컴퓨터와 5번 컴퓨터를 연결함으로써 각 지사 컴퓨터간의 MST가 형성된다.

---

5. 코드