[알고리즘 문제] 1272번 특별 노드

1272번: 특별 노드

 

1. 접근 과정

1-1) 실패 과정 1

처음에 대충보고 그리디인가? 생각했었는데 위의 노드에 상황에 따라 그 하위의 노드들을 고르는 기준이 달라지는 것을 통해 5분도 안되서 첫 번째 아아디어가 아님을 알 수 있었다.

 

1-2) 실패 과정 2

위의 실패를 통해 [특별노드][노드번호] 로 dynamic table을 세우면 되겠지 싶었고 tree dp에 대해 경험이 부족했던 나는 위 해법이 2^1000 꼴로 중복해서 계산하면 어쩌지... 라는 마음에 다른 방법을 생각하게 되었다. (사실 저 방법이 정답이었다..)

 

1-3) 실패 과정 3

위 실패를 통해 dt[special_node] 꼴로 dynamic table을 세워서 아래 자식들은 현재 가능한 모든 부모에 대해 dt[parent] += w[node] - w[parent] 꼴로 다 계산하면 괜찮지 않을까? 싶었지만 이 dt로는 아래 상황을 서술하기에 충분한 정보를 가지고 있지 않다는 사실을 통해 2차원이 옳지 않을까 생각하였다.

 

2) 성공

위의 실패를 통해 2차원에 대해 다시 접근하게 되었고 쫌 더 고찰해본 결과 어떤 node가 spec일 경우 이는 그냥 서브트리로 따로 찢어놓고 생각해도 된다는 것이다. 예전에 dp와 dfs/bfs 를 활용한 문제를 풀었던 기억을 통해 dp를 이용하면 이런 중복의 경우를 줄일 수 있다는 사실을 뒤늦게 깨달았다... 

 

 

2. 해설

dt[node][spec] = 어떤 node에 대하여 그의 특별 노드가 spec일 경우 가중치 합의 최솟값으로 정의하였다. 그리고 모든 가능성을 확인하기 위해 해당 노드가 spec일 경우와 아닐경우로 나누어서 계산하고 dt[node][spec]를 갱신하고 dfs에서 return해준다. 

 

3. 코드

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

int N, M, w[1005], dt[1005][1005];
vector<int> v[1005], p;

int process(int node, int before, int spec)
{
    if(dt[node][spec]) return dt[node][spec];
    int here = w[node], other = w[node] - w[spec];
    for(auto&i:v[node]){
        if(i == before) continue;
        here += process(i, node, node);
        other += process(i, node, spec);
    }
    return dt[node][spec] = min(here, other);
}

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

    int x, y, ans=0;
    cin >> N >> M;
    for(int i=1;i<=N;i++) cin >> w[i];
    for(int i=1;i<N;i++){
        cin >> x >> y;
        v[x].push_back(y); v[y].push_back(x);
    }
    for(auto&i:v[M]) ans += process(i, M, M);
    cout << ans + w[M];
}

 

4. 소감

트리 dp는 일반 dp랑 다를거라 생각하고 계속 이상하게 접근했다. 일반적인 dp는 그냥 index가 차례대로 올라가지만 tree dp의 경우 index가 children으로 바뀐거에 지나지 않는다는 사실을 알 수 있었다. 그리고 dfs/bfs와 dp를 활용해 모든 가지 수를 생각하되 O[(a^N)] 꼴이 안되게 만들 수 있다는 사실을 다시 상기시킬 수 있었다... 그리고 생각해보니 dfs/bfs dp 를 많이 안풀어봤는데 tree dp.. 많이 풀어봐겠다...