백준 1272번: 특별 노드

https://www.acmicpc.net/problem/1272

 

부모보다 자식의 가중치가 더 큰 트리가 주어질 때, 루트 노드를 포함한 특별 노드를 선택해서 특별 노드들을 제외한 노드들의 부모 노드 중 가장 가까운 특별 노드의 가중치를 뺀 값이 해당 노드의 가중치가 될 때 가중치 합의 최소값을 구하는 문제이다.

누적합을 위한 2차원 배열 dp와 DFS를 통해 트리의 맨 아래부터 일반 노드로 만들 때와 특별 노드로 만들 때의 해당 노드까지의 가중치 합의 최소값을 구하여 누적한다. dp[a][b]는 가장 가까운 특별 노드인 부모 노드가 b일 때, 현재 노드 a에서의 최소값을 의미한다.

static int solve(int curr, int specialAnc, int parent) {
    if (dp[curr][specialAnc] != -1) {
        return dp[curr][specialAnc];
    }
    
    int nodeNotSpecial = INF;
    if (curr != root) {
        nodeNotSpecial = weights[curr] - weights[specialAnc];
        for (int next : map.get(curr)) {
            if (next == parent) {
                continue;
            }
            nodeNotSpecial += solve(next, specialAnc, curr);
        }
    }
    
    int nodeSpecial = weights[curr];
    for (int next : map.get(curr)) {
        if (next == parent) {
            continue;
        }
        nodeSpecial += solve(next, curr, curr);
    }
    
    return dp[curr][specialAnc] = Math.min(nodeNotSpecial, nodeSpecial);
}

 

현재 노드를 특별 노드로 선택하지 않은 경우 현재 가중치 - 가장 가까운 특별 노드 가중치 + 선택 하지 않았을 때의 자식 노드들의 최소 가중치로 계산허며, 선택한 경우 현재 가중치 + 선택한 경우의 자식 노드들의 최소 가중치 로 계산하여 최소값을 구하여 둘 중 최솟값을 저장하는 방식으로 누적한다.