요즘, 동숲과 메이플에 빠져 있다. 그래서 문제도 'MST 게임'을 풀이해볼까 한다. (억지 연계)

BOJ 16202 - MST 게임 링크
(2022.09.19 기준 G4)
(치팅 노노해)

문제

K턴 동안의 MST 가중치의 합을 출력. 단, 턴마다 만들어진 MST의 최소 가중치 간선 하나를 제거한다. 그리고 MST가 만들어지지 않으면 가중치의 합은 0으로 한다.

알고리즘

MST를 턴마다 만들어야 한다. 그리고 한 턴마다 제일 가중치가 작은 간선을 제거해나가야 한다.

풀이

특별힌 테크닉은 없다.
K턴 동안 MST를 만들어서 가중치의 합을 구하면 되고, 그 MST의 제일 가중치가 작은 간선을 앞으로 못쓰게 만들면 된다. 간선 자체를 못쓰게 만들어야 하므로, 간선 위주의 알고리즘인 크루스칼을 쓰도록 하자.

간선의 가중치는 입력 순서대로 1, 2, ..., M이다. 이는 오름차순으로 정렬되어 있다는 것이므로 따로 정렬할 필요는 없다. 그리고 간선 번호가 가중치라고 생각하자.

K만큼 for문을 돌면서 MST를 만들 때, 제일 처음으로 쓰이는 간선의 가중치(번호)를 따로 저장해두자. 그리고 나중에 MST가 완성되면 저장된 간선을 앞으로 못쓰게 만들면 된다. visited 배열 기법의 반대라고 생각하자.

for u, v, w in edges: # 간선을 차례대로 살펴보고
    if possible[w] and find(u) != find(v): # 사용 가능한 간선이며, 부모 노드가 다를 경우

MST가 만들어지지 않았다면, 앞으로 턴을 진행시킬 필요가 없으므로 게임 자체를 종료하자.

코드

# 크루스칼
import sys; input = sys.stdin.readline

def find(u):
    if parent[u] != u:
        parent[u] = find(parent[u])
    return parent[u]

def union(u, v):
    u = find(u)
    v = find(v)
    if u < v:
        parent[v] = u
    else:
        parent[u] = v

N, M, K = map(int, input().split())
# 간선의 가중치는 주어지는 순서대로 1, 2, ..., M이다.
# 가중치의 순서는 오름차순이므로 따로 정렬할 필요는 없다.
edges = [list(map(int, input().split())) + [m] for m in range(1, M + 1)]
possible = [True] * (M + 1) # 간선이 사용 가능한지를 저장할 배열
answer = [0] * K # 턴마다, 가중치의 합

# K만큼의 턴을 시작
for turn in range(K):
    parent = list(range(N + 1)) # 부모 노드
    MIN = -1 # 제일 작은 가중치이자 간선의 번호
    result = ct = 0 # 가중치의 합, 연결된 간선의 개수
    for u, v, w in edges:
        if possible[w] and find(u) != find(v): # 사용 사능한 간선이자 부모 노드가 다르면 union
            if MIN == -1: # 제일 작은 가중치가 갱신이 되지 않았다면 저장
                MIN = w
            union(u, v)
            result += w
            ct += 1
            if ct == N - 1: # 연결된 간선의 개수가 N - 1개가 되었다면 MST가 완성이 되었으므로 턴 종료 및 결과 입력
                answer[turn] += result
                possible[MIN] = False # 제일 작은 가중치이자 간선의 번호는 더 이상 사용 불가능
                break
    else: # 만약 MST가 완성되지 않았다면 게임 종료
        break
print(*answer)

여담

시간 초과가 나지 않을까란 걱정관 달리, 아주 넉넉하게 AC를 받은 문제. 난 역시 잘해.