BOJ 8872(빌라봉)풀이

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

문제를 요약하면 기존 입력에 N-M+1 개의 가중치가 L 인 간선을 추가로 만들어 모든 점끼리 갈 수 있게 할 때 두 빌라봉을 오가는데 드는 비용 중 가장 큰 값이 가장 작도록 N-M+1 개의 간선을 만드는 것이다.  즉 그래프가 1개 이상이라는 것인데 이때 각 그래프에서 점 하나를 골랐을 때 그 점과 한 그래프의 나머지 점들끼리의 거리의 최댓값이 가장 작은 점을 고른 뒤 한 그래프를 한 점이라고 했을 때 점들을 연결했을 때 점들 간의 거리의 최댓값이 가장 작아야 되기 때문에 점이라고 정의한 그래프의 값 중 가장 큰 값을 중앙에 두고 중앙을 중심으로 다른 점들이 중앙 점과 연결을 할 때 가장 작은 값을 찾을 수 있다. 맨 처음 그래프 내에서 거리의 최댓값이 가장 작은 값을 고르는 방법은 이전에 설명했던 사무실 이전 이라는 문제를 풀 때 사용한 방식을 이용하면 된다.

 

한 그래프에서 한 점을 루트 노드로 잡고(이 그래프들은 사이클은 생기지 않기 때문에 한 점을 루트 노드로 잡아주면 트리가 된다.) 탐색을 하면서 자신과 자식들 간의 거리 중 가장 큰 값을 저장한다. 그다음에 다시 한번 같은 루트 노드를 중심으로 탐색을 하는데 위에 코드에선 자신의 자식 노드들과 거리의 max를 구했다면 이번에는 그 노드들은 제외한 노드들 간의 max를 구해줘야 한다.

 

이건 트리를 내려오면서 자신의 i번째 자식으로 탐색을 한다고 했을 때 i번째 자식을 제외한 다른 자식들에게 저장되어있는 max 값 중 가장 큰 값을 i번째 자식을 지날 때 드는 비용을 더해서 내려주면 어떤 노드에 대해 그 노드의 부모 노드들이나 그 외 부모 노드들에 연결되어있는 다른 노드들 간의 max를 구할 수 있게 된다.

 

자신을 제외한 max 값은 맨 처음에 자식들의 max를 구하면서 가장 큰 값과 그다음으로 큰 값을 저장하면 i번째 자식이 가장 큰 값이라면 i번째를 제외한 max는 두번째로 큰값이 되고 아닐 경우 반대로 가장 큰값이 제외한 점들중 큰값이 된다.

그렇게 내려갈 때마다 앞에서 구했던 자식들 간의 max와 지금 구해준 값 중 max값을 골라주면 된다. 이렇게 모든 탐색을 마치고 이 값들을 저장한 배열을 보면 i번째 점을 골랐을 때 다른 점들 간의 거리 중 max 값이 들어있게 된다.

그렇기 때문에 그중 가장 작은 값을 골라주게 되면 위에서 말한 점을 구할 수 있게 된다.

 

이렇게 각 그래프 간의 가장 짧은 거리를 구해줬으면 이제 그 값들 중 가장 큰 값을 중심으로 다른 값들을 큰 값이랑 이어주면 된다. 물론 그래프를 만들 필요는 없고 각 그래프들의 트리 지름 중 가장 큰 값만 있으면 된다. 트리 지름은 이전에 다룬 문제 중에 트리 지름이라는 문제가 있는데 그 문제 풀이 글을 보거나 문제를 풀고 와야지 이 문제를 푸는데 도움이 된다.  트리의 지름을 구하는 이유는 두 그래프 간의 거리가 최대 거리가 아닌 한 그래프 안에서의 거리가 최대가 될 수 있기 때문이다. 

이제 값을 구해주면 된다. 그래프의 개수가 1개일 때는 트리 지름이 가장 거리가 먼 게 되기 때문에 트리 지름 값을 출력해주고 그래프의 개수가 2개일 때는 가장 긴 트리 지름과 두 그래프 값의 합+L을 비교해서 더 큰 값을 출력해주고 개수가 3개 이상일 때는 2개일 때와 같은 조건에 가장 큰 값이 아닌 2,3번째로 큰 값들의 합+L*2를 비교해준다. L, L*2를 비교해주는 이유는 앞에서 가장 큰 값을 중심으로 다 큰 값이랑 이어줬기 때문에 큰 값과 나머지 값들 간의 거리 값은 L 이 되고 큰 값이 아닌 다른 값들간의 거리 값은 L*2이 되기 때문에 두 그래프 값을 더한 값에 L, L*2를 더해주는 것이다.

 

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct nd{
    ll next,va;
};
vector<nd>graph[100500];
vector<ll>sk;
ll dp[100500],dp1[100500];
pair<ll,ll> st[100500];
ll ch[100500];
ll ans=1e11;
ll lans=0;
ll lp[100500];
ll max(ll a,ll b){
    if(a>b)return a;
    else return b;
}
ll min(ll a,ll b){
    if(a>b)return b;
    else return a;
}
void dfs(ll n,ll lt){
    ch[n]=1;
    ll fm=0,sm=0,vl=0;
    ll fm2=0,sm2=0,v2=0;
    nd Q;
    ll ma=0;
    for(int i=0;i<graph[n].size();i++){
        Q=graph[n][i];
        if(Q.next!=lt){
            dfs(Q.next,n);
            vl=dp[Q.next]+Q.va;
            if(vl>=fm){sm=fm;fm=vl;}
            else if(vl>sm)sm=vl;
            v2=lp[Q.next]+Q.va;
            if(v2>=fm2){sm2=fm2;fm2=v2;}
            else if(v2>sm2)sm2=v2;
            ma=max(ma,v2);
        }
    }
    st[n].first=fm;
    st[n].second=sm;
    dp[n]=fm;
    lp[n]=ma;
    lans=max(lans,fm2+sm2);
}
void dfs1(ll n,ll lt,ll v){
    ll val=0;
    dp1[n]=max(v,dp[n]);
    ans=min(ans,dp1[n]);
    nd Q;
    for(int i=0;i<graph[n].size();i++){
        Q=graph[n][i];
        if(Q.next!=lt){
            if(dp[Q.next]+Q.va==st[n].first)val=st[n].second;
            else val=st[n].first;
            dfs1(Q.next,n,max(v,val)+Q.va);
        }
    }
}
int main()
{
    fill(ch,ch+100500,0);
    fill(dp,dp+100500,0);
    fill(dp1,dp1+100500,0);
    ll N,M,L,A,B,T;
    scanf("%lld %lld %lld",&N,&M,&L);
    for(int i=0;i<M;i++){
        scanf("%lld %lld %lld",&A,&B,&T);
        graph[A+1].push_back({B+1,T});
        graph[B+1].push_back({A+1,T});
    }
    for(int i=1;i<=N;i++){
        if(ch[i]==0){
            ans=1e11;
            dfs(i,-1);
            dfs1(i,-1,0);
            sk.push_back(ans);
        }
    }
    sort(sk.begin(),sk.end());
    reverse(sk.begin(),sk.end());
    ll jk=sk.size();
    if(jk==1)printf("%lld\n",lans);
    else if(jk==2)printf("%lld\n",max(lans,sk[0]+sk[1]+L));
    else{
        printf("%lld\n",max(lans,max(sk[0]+sk[1]+L,sk[1]+sk[2]+L*2)));
    }
 
}