[BOJ/백준] 23034 조별과제 멈춰! 파이썬

문제 링크 : https://www.acmicpc.net/problem/23034

23034번: 조별과제 멈춰!

 

MST와 BFS로 풀었다.

 

처음에는 단순하게 MST 구성해서 가중치 합 구하고

x,y의 간선 정보만을 보고 빼주면 될줄 알고 제출했더니 틀렸다.

 

당연하다. 문제는 두개의 점을 기준으로 두개의 MST를 만드는 것이다. 그래서 모든점을 포함하는 MST를 구성하고, 두 점을 기준으로 두개의 MST로 나누어야한다.

따라서 두 점 사이의 간선 중 가중치가 가장 큰 것을 빼주면 두개의 MST가 생성된다.

 

그래서 BFS로 모든점에서 각 점까지 도달했을 때 거쳐간 간선 중 가중치가 가장 큰것을 구했다.

그리고 이정보를 가지고 MST의 가중치의 합에서 두 지점사이의 최대 가중치를 빼주었다.

 

from sys import stdin
from collections import deque

input = stdin.readline

n,m = map(int, input().split())
adj_list = [[] for _ in range(n+1)]
max_cost_board = [[-1]*(n+1) for _ in range(n+1)]

edges = []
for _ in range(m):
    a,b,c = map(int, input().split())
    edges.append((a,b,c))

edges.sort(key=lambda x:x[2])

parent = [i for i in range(n+1)]
def solv():
    q = int(input())
    total_cost = kruskal()
    set_max_cost_board()

    for _ in range(q):
        a,b = map(int, input().split())
        print(total_cost-max_cost_board[a][b])
def set_max_cost_board():
    for start in range(1,n+1):
        bfs(start)

def bfs(start):
    global max_cost_board
    max_cost_board[start][start] = 0

    q = deque([(start,0)])

    while q:
        now, max_cost = q.pop()

        for nxt, cost in adj_list[now]:
            if max_cost_board[start][nxt] == -1:
                tmp_max_cost = max(max_cost,cost)
                max_cost_board[start][nxt] = tmp_max_cost
                q.appendleft((nxt,tmp_max_cost))
def kruskal():
    global adj_list
    edge_count = 0
    cost = 0
    for a,b,c in edges:
        if not is_same_parent(a,b):
            union(a,b)
            edge_count += 1
            cost += c
            adj_list[a].append((b,c))
            adj_list[b].append((a,c))
            if edge_count == n-1:
                return cost
def find(target):
    global parent
    if parent[target] == target:
        return target
    parent[target] = find(parent[target])
    return parent[target]

def union(a,b):
    global parent
    a = find(a)
    b = find(b)

    if a != b:
        parent[a] = b

def is_same_parent(a,b):
    return find(a) == find(b)

solv()