[파이썬/python] SWEA - 26504 MST 만들기

 

문제

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AZz7FPpqAUnHBIRj

---

문제 설명

1. N개의 정점은 가진 방향성 없는 그래프가 주어진다.
   1. 서로 다른 정점 쌍이 정확히 1개의 간선으로 이어져 있다.
   2. 총 $N(N-1)/2$ 개의 서로 다른 간선이 있는 완전 그래프다.
   3. 각 간선은 양의 정수 가정치를 가진다.
2. 해당 그래프에서 최소 스패닝 트리를 계산해야 한다.
3. 어떤 간선에 어떤 가중치가 있는지 모르며, 가중치만 리스트로 주어진다.
4. 모든 가중치를 간선에 배치했을 때, MST의 최소 비용과 최대 비용을 구한다.

 

---

풀이

문제를 이해하는데 많은 시간을 사용했다.

 

MST는 N개의 노드가 존재할 때 N-1개의 간선을 사이클이 존재하지 않도록 이어 최소 가중치가 되도록 구성하는 트리이다.

 

그렇기 때문에 최소 비용은 가중치들을 오름차순으로 정렬했을 때 앞에서부터 N-1개를 선택하면 된다.

 

최대 비용은 이야기가 다르다. 이 부분에서 시간을 많이 썼다.

 

처음에는 단순히 큰 가중치를 N-1개 선택하면 되는 것 아닌가? 라고 생각했다.

하지만 이 문제의 핵심은 MST의 최댓값을 구하는 것이다.

 

MST는 결국 최소 가중치의 스패닝 트리이기 때문에, 최솟값중 최대가 되는 경우를 찾으라는 말이다.

 

그럼 최대가 되려면 어떻게 해야 하는지 구해보자.

 

MST의 특성상 작은 간선부터 선택할 수 밖에 없다. 즉 1부터 순차적으로 선택하게 될 것이다.

하지만 우리는 최소를 만드는 와중에 최대가 되도록 중간 중간 브레이크를 걸어줘야 한다.

 

즉 최대한 작은 숫자들이 버려지고 큰 숫자를 선택할 수 있도록 해야한다는 말이다.

 

작은 숫자를 버리기 위해서는 최대한 많은 사이클을 만들어 낮은 숫자를 버리도록 해야 한다.

 

아래 예시를 통해서 한 번 구해보자.

N = 5, [1,2,3,4,5,6,7,8,9,10]의 간선이 존재한다.

이 경우에는 총 4개의 간선을 이어야 한다.

 

사이클이 만들어진다는 것은, 삼각형, 사각형... N각형을 만드는 것이다.

 

최초 사이클을 만들기 위해서는 삼각형을 만들어야 하므로 최초 2개의 간선은 필수로 입력된다.

따라서 0, 1번 간선을 입력한다.

 

2번 간선은 삼각형 사이클을 만들 수 있으므로 Skip한다.

 

3번 간선은 아직 사이클을 만들 수 없으므로 입력한다.

 

4번 간선은 삼각형 사이클을 만들 수 있으므로 Skip한다.

 

5번 간선은 사각형 사이클을 만들 수 있으므로 Skip한다.

 

6번 간선은 아직 사이클을 만들 수 없으므로 입력한다.

 

7,8,9번은 각각 삼각형, 사각형, 오각형 사이클을 만들 수 있으므로 Skip한다.

 

10번 간선은 아직 사이클을 만들 수 없으므로 입력한다.

 

위와 같은 결과를 보면 아래와 같은 규칙을 발견할 수 있다.

 

간선이 입력될 때 마다 사이클의 개수가 1개씩 늘어나며 사이클이 완성된 후 다음 간선을 더한다.

 

따라서 0,1,3,6,10..의 간선을 더하면 최대 가중치를 구할 수 있다.

즉 $i(i-1) / 2$번째 인덱스를 더하면 되는 것이다.

 

최소 비용은 쉽게 구했지만, 최대 비용은 직접 그림을 그려보고 어떤 가중치를 버려야 하는지 고민해야 알 수 있는 문제였다.

 

처음 문제를 이해할 때 MST의 특성을 잊어버리고, 최대 비용에 대해 오래 고민해서, 문제를 푸는데 오래 걸렸다.

 

유사 문제가 나왔을 때 최소중에 최대를 구하는 것을 잊지 않도록 해야겠다.

---

코드

import sys
input = sys.stdin.readline

for tc in range(int(input())):
    N = int(input())
    edges = sorted(list(map(int,input().split())))
    min_cost = sum(edges[:N-1])
    if N < 4:
        max_cost = min_cost
    else:
        max_cost = 0
        for i in range(1,N):
            idx = (i*(i-1) // 2)
            max_cost += edges[idx]

    print(min_cost, max_cost)

---

시간복잡도

• 각 입력마다 최대 N번의 연산을 진행한다.
• 최악의 경우 $N = 100$, 즉 $O(10^2)$의 시간복잡도가 소요된다.