[알고리즘 문제] 27730번 견우와 직녀

최근에 이 문제를 풀고 큰 교훈을 얻어서 올려야지~ 하고 못했던 문제 중 하나입니다.. 복습할 문제들 보다가 이 문제가 눈에 띄어서 다시 올려봅니다.

27730번: 견우와 직녀

 

 

1. 문제 분석

A트리와 B트리가 존재할 때 A트리의 임의 노드 a, B트리의 임의 노드 b에 대하여 A의 모든 노드와 B의 모든 노드를 이동하는 비용의 합은 B.size * ( i -> a ) + A.size * (j -> b) + A.size * B.size 입니다. 그리고  i -> a 와 j -> b는 모두 독립이므로 각각 따로 구해주면 됩니다. 그럼 최소가 되는 a와 b점을 찾으면 답을 구할 수 있습니다.

 

전체적인 문제 해석에는 틀린 점은 없고 실패 과정도 맞는 방법이었는데... 제가 이상하게 뺑뺑 돌아가는 과정이었습니다.

 

 

2. 실패 과정

1번의 dfs로 dt를 채우고자 하였습니다. 그렇기 때문에 순방향과 역방향의 계산을 전부 다 해야할 뿐더러 이미 한 노드에 대해 값이 이미 전부 갱신된 것이 아니기에 애초에 불가능한 방법이었다. 이로 인해 1시간 넘게 삥삥 돌았습니다..

 

 

3. 성공 과정

적어도 1개의 노드에 대해서 계산이 이미 다 되있다면 어떨까 하여 아래와 같이 그림을 그리며 나타내었고 첫 번째 dfs를 통해 초기값을 설정하고 다음 dfs를 통해 dt를 채우도록 설정했다.

 

그랬더니 이미 계산한 노드로 부터 인접 노드로 목적지를 바꿀 때 해당 간선을 지나는 횟수가 얼마나 늘어나고 줄어드는지를 통해 계산을 매우 쉽고 간편하게 할 수 있었다.

 

 

 

4. 코드

#include <bits/stdc++.h>
using namespace std;

#define ll long long int
#define pii pair<int,int>
#define MAX 100005
ll N[2], T, cnt[2][MAX];
vector<pii> v[2][MAX];
ll dt[2][MAX], ans, min_value[2];

ll init(int n, int bef)
{
    ll sum = 0;
    for(auto&i:v[T][n]){
        if(i.first==bef) continue;
        sum += init(i.first, n) + (ll)cnt[T][i.first] * i.second, cnt[T][n] += cnt[T][i.first];
    }
    cnt[T][n]+=1;
    return sum;
}

void process(int n, int cost, int bef)
{
    dt[T][n] = dt[T][bef] - (ll)cost * ( 2*cnt[T][n] - N[T]);
    for(auto&i:v[T][n]){
        if(i.first == bef) continue;
        process(i.first, i.second, n);
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    int x, y, cost, loc[2];
    for(T=0;T<2;T++){
        cin>>N[T];
        for(int j=1;j<N[T];j++){
            cin>>x>>y>>cost;
            v[T][x].push_back(pii(y,cost));
            v[T][y].push_back(pii(x,cost));
        }
        dt[T][1] = init(1, 0), min_value[T] = 21e8*21e8;
        for(auto&i:v[T][1]) process(i.first, i.second, 1);
        for(int i=1; i<=N[T]; i++){
            if(min_value[T] > dt[T][i]){
                min_value[T] = dt[T][i];
                loc[T] = i;
            }
        }
    }
    cout << loc[0] << " "<<loc[1] <<"\n";
    cout <<min_value[0]*N[1] + min_value[1]*N[0] + N[1]*N[0];
}

5. 소감 및 교훈

살짝 완벽주의 성격이랑 한 번에 처리하자! 라는 생각이 쫌 많았었는데.. 이번 문제를 경험하면서 초기값 갱신이 매우 중요하기에 초기에 dfs한번 도는 것을 아까워 해선 안된다는 것을 느낄 수 있었다.

 

또한 해당 문제는 다른 tree dp 랑 느낌이 달랐는데, 다른 tree dp 는 다음 노드를 루트로 하는 부분 트리에 대해서 쪼개는 방식이었다면 이번에는 기존의 값을 통해 계산하는 memorization느낌이 나는 dp를 배울 수 있었다.