BOJ 23034(조별과제 멈춰!) 풀이

이미지를 누르면 문제로 이동합니다

 

요약하면 그래프가 주어지고, Q개의 쿼리에서 X, Y 가 주어지면 X, Y에서 시작하는 스패닝 트리의 최솟값을 구하라는 문제이다. 기존 스패닝 트리와는 다르게 두 점 X, Y에서 스패닝 트리가 시작할 수 있는데 이는 즉, 한 그래프 안에서 스패닝 트리가 2개가 나올 수도 있다는 소리가 된다.

그럼 이를 어떻게 해결할 수 있을까?

 

그 방법은 스패닝 트리의 특징을 생각해보면 알 수 있다. 스패닝 트리는 N개의 점에 대해 N-1 개의 간선을 가진다.

 

또 문제에선 X,Y 에서 시작하는 최소 스패닝 트리를 요구하기 때문에 N-1 간선에서 최대 1개의 간선을 제거할 수 있다. 간선을 2개 이상 제거 할 경우, 어떠한 점을 연결할 수 없게 된다. 그러므로 최대 선 1개만 지울 수 있다,

음수 가중치가 없기 때문에 선을 1개를 지우는 것이 0개를 지우는 것보다 최소 값을 만들 수 있는건 자명하다.

또 스패닝 트리를 X,Y 에서 시작하기 때문에 X와 Y는 굳이 연결되어 있을 이유가 없다. 그렇기 때문에 X와 Y를 두 개의 스패닝 트리로 나누는 값이 최소 스패닝 트리를 가지게 된다.(X 혼자 떨어지는 경우도 X 하나의 스패닝 트리라고 본다)

그럼 어떤 선을 지워야지 최소값을 구할 수 있을까?

 

선을 지우는 방법에는 두가지가 있다. 

1. X 와 Y 가 바로 연결되어 있는 경우

2. X 와 Y 가 바로 연결되어 있지 않은 경우

 

1번의 경우에선 X와 Y를 연결하는 선을 지워야 한다. 

그 이유는 간단한데, 선을 1개를 지운다고 했을 때, XY 선이 아닌 다른 선을 지운다면 그 선으로부터 연결된 점들에 X, Y에서 도달하지 못해 스패닝 트리를 이룰 수 없게 된다. 그렇기에 X와 Y를 연결하는 선이 있다는 그 선을 지워야 한다.

 

2번의 경우에는 선을 지우지 않았을 때의 최소 스패닝 트리 경로에서 DFS 탐색을 통해 X에서 Y 로 가면서 지나간 선의 가중치의 max를 빼주면 된다. 

X와 Y 가 연결되어 있지 않고, X와 Y를 2개의 스패닝 트리로 분리해야 되기 때문에 X에서 Y로 가는 선중 가장 큰 가중치를 가지는 선을 지운다면 위 조건을 모두 만족하면서 최솟값을 구할 수 있다.

 

N의 범위도 1000까지 밖에 되지 않기 때문에 점 마다 DFS 탐색해도 문제없다.

DFS 탐색을 통해 X에서 Y로 가는 구간중 최댓값을 2차원 배열에 저장 후 쿼리 Q마다 전체 최소 스패닝 트리에서 입력에 해당되는 값을 빼주면 된다.

 

import sys,math
inf=math.inf
sys.setrecursionlimit(10**9)
n,m=map(int,input().split())
uf=[-1]*(n+1)

def find(a):
    if uf[a]<0:return a
    uf[a]=find(uf[a])
    return uf[a]
def merge(a,b):
    a=find(a)
    b=find(b)
    if a==b:return 0
    uf[b]=a
    return 1
def dfs(x,St,mx):
    global x2y_cost
    st[x]=1
    for i in range(len(mst[x])):
        nt=mst[x][i][0]
        if st[nt]==0:
            x2y_cost[St][nt]=max(mx,mst[x][i][1])
            dfs(nt,St,x2y_cost[St][nt])


adj=[]
for i in range(m):
    b,c,d=map(int,input().split())
    adj.append([d,b,c])
adj.sort()
uf=[-1]*(n+1)
rt=0
cnt=0
mst=[[] for i in range(1005)]
x2y_cost=[[0 for i in range(1002)]for g in range(1002)]
for i in range(m):
    u=adj[i][1]
    v=adj[i][2]
    cost=adj[i][0]
    if merge(u,v):
        rt+=cost
        mst[u].append([v,cost])
        mst[u].append([v,cost])
        cnt+=1
        if cnt==n-1:break

for i in range(n):
    st=[0]*(1003)
    dfs(i+1,i+1,-inf)

q=int(input())
for i in range(q):
    X,Y=map(int,input().split())
    print(rt-x2y_cost[X][Y])