[SWEA] 26504. MST 만들기

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AZz7FPpqAUnHBIRj&categoryId=AZz7FPpqAUnHBIRj&categoryType=CODE&problemTitle=&orderBy=FIRST_REG_DATETIME&selectCodeLang=ALL&select-1=&pageSize=10&pageIndex=1

SW Expert Academy

T = int(input())

for _ in range(T):
    N = int(input())
    costs = list(map(int, input().split()))
    
    costs.sort()
    
    min_mst = sum(costs[:N-1])
    
    max_mst = 0
    for i in range(N-1):
        index = (i * (i + 1)) // 2
        max_mst += costs[index]
    
    print(min_mst, max_mst)

MST(Minimum Spanning Tree, 최소 신장 트리)

Spanning Tree(신장 트리)

그래프의 모든 정점을 포함하면서, 사이클이 없는 부분 그래프 

간선의 수 = 정점의 수 - 1 

 

MST(Minimum Spanning Tree, 최소 신장 트리)

가능한 모든 신장 트리 중에서 간선 가중치의 합이 최소인 트리 

 

최소 비용

가중치를 오름차순으로 정렬 후, 간선의 개수인 n-1 개만큼 선택하면 된다. 

Star 구조로 배치한다고 생각하면 쉽다. 

최대 비용

정점을 추가할 때마다 이전 정점들 사이 간선에 작은 가중치를 배치해 사이클로 건너뛰게 만든다. 

말이 어려운데, 그림으로 표현해보면,  

3개의 노드가 2개의 간선으로 연결된 상황에서 4번째 노드를 추가하려 할 때, 최소 비용처럼 계산하지 않고 

그림과 같이 최대한 사이클을 형성해 작은 가중치들을 제거하는 것이 목표이다. 

 

만약, 노드의 개수가 4개가 아닌 5개라고 가정한다면, 아래와 같은 모양이 나타날 것이다. 

그림과 같이 정점을 순차적으로 추가하면서 이전 정점들 사이에 작은 가중치를 배치하고 사이클을 형성해 건너뛰게 만드는 것이다. 

 

지금까지의 간선 패턴을 보면 정점을 하나씩 추가할 때마다 이와 같은 패턴을 보이는데,  

i=0 (1번째 간선): 
  - 사용 가능한 간선 범위: 0개
  - 인덱스 = 0

i=1 (2번째 간선):
  - 사용 가능한 간선 범위: 0~1 (2개)
  - 인덱스 = 1

i=2 (3번째 간선):
  - 사용 가능한 간선 범위: 0~3 (4개)
  - 하지만 0,1은 이미 썼고, 2는 사이클
  - 인덱스 = 3

i=3 (4번째 간선):
  - 사용 가능한 간선 범위: 0~6 (7개)
  - 하지만 0,1,3은 이미 썼고, 2,4,5는 사이클
  - 인덱스 = 6

 

이를 공식화하면 index = i * (i + 1) // 2 로 나타낼 수 있다. 

따라서, i가 증가할 때마다 해당 인덱스 값을 더해주면 된다. 

 

문제 풀이로 아래 블로그의 도움을 많이 받았다. ↓

https://positecoding.tistory.com/127

SWEA 26504. MST 만들기