백준 1949 : 우수마을 - javascript(트리, dp)

문제 출처 

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

 

정답 풀이 

백준의 "우수마을" 문제는 트리 DP(dynamic programming on trees)를 사용하는 전형적인 문제입니다. 이 문제는 트리를 기반으로 우수 마을을 선정하여 마을 주민 수의 최대합을 구하는 문제입니다.

문제 접근 방법:

1. 각 마을이 트리 형태로 연결되어 있다는 점을 이용해 DFS 탐색을 기반으로 DP를 적용해야 합니다.
2. 각 마을은 우수 마을이 될 수도 있고, 아닐 수도 있습니다.
3. 우수 마을이 될 경우, 이 마을과 연결된 다른 마을은 우수 마을이 될 수 없습니다.
4. 각 마을을 우수 마을로 선정하는 경우와 그렇지 않은 경우를 나눠서 DP로 해결합니다.

알고리즘

1. 트리에서 DP를 사용하기 위해 DFS로 각 노드를 탐색합니다.
2. 각 마을에 대해 우수 마을로 선정된 경우와 아닌 경우를 나눠서 DP 값을 저장합니다.
   • dp[i][0]: 마을 i가 우수 마을이 아닌 경우의 최대 주민 수
   • dp[i][1]: 마을 i가 우수 마을인 경우의 최대 주민 수
3. DFS로 자식 노드들을 탐색하며 DP 값을 갱신해 나갑니다.

정답 코드 

const input = require('fs').readFileSync('/dev/stdin').toString().trim().split('\n'); 
const n = Number(input.shift()); 
const people = input.shift().split(' ').map(v => +v); 
const tree = Array.from({length: n+1}, () => [])
const dp = Array.from({length: n+1}, () => [0,0])
const visited = new Array(n+1).fill(false)

for(let i=0; i<n-1; i++){
    let [a,b] = input[i].split(' ').map(v => +v)
    tree[a].push(b); 
    tree[b].push(a); 
}

function solution(n,people, tree){

    function dfs(node){
        visited[node] = true; 
        dp[node][0] = 0 //해당 마을 우수 선정 x
        dp[node][1] = people[node-1] //해당 마을 우수 선정 o 
        
        for(let next of tree[node]){ //인접 마을 탐색 
            if(!visited[next]){ //방문하지 않았을때 
                dfs(next) //방문
                dp[node][0] += Math.max(dp[next][0],dp[next][1]) //자식이 우수마을 일 때 아닐 때 중 큰 값
                dp[node][1] += dp[next][0] //자식이 우수마을이 아니여야 함 
            }
        }
    }
    dfs(1)
    return Math.max(dp[1][0], dp[1][1])
}

console.log(solution(n,people, tree))


//dfs 완탐? 선정 or 선정 x 
//전체 배열 다 돌면 그때의 합 구하기 
//그 후 


//주민 수 최대로 
//우수마을 인접 x 
//적어도 하나의 우수마을과 인접

 

추가 설명 

 

이 문제는 트리 구조에서 DFS를 이용해 최종적으로 계산된 DP 값이 각 노드마다 제대로 저장되는 방식입니다. 하지만 왜 dfs(1)로 탐색을 시작했다면 **반드시 루트 노드(1번 마을)**에 대해 최종 결과를 구해야 하는지, 그리고 왜 dp[2][0], dp[2][1]으로 출력할 수 없는지에 대해 설명드리겠습니다.

1. DFS 탐색의 역할

DFS는 루트에서 시작하여 트리의 모든 자식 노드를 탐색하면서 자식 노드의 결과를 부모 노드로 합산합니다. 이 과정에서 DP 배열은 각 노드가 우수 마을이 될 때와 되지 않을 때의 최대 주민 수를 기록하게 됩니다.

예를 들어, 1번 마을을 루트로 설정한 경우:

• dfs(1)로 시작하면, 1번 마을을 기준으로 모든 자식 노드들(예: 2번, 3번 등)에 대한 결과가 dp[1][0], dp[1][1]에 저장됩니다.
• **dp[1][0]**은 1번 마을이 우수 마을이 아닐 때의 최대 주민 수를 의미하고,
• **dp[1][1]**은 1번 마을이 우수 마을일 때의 최대 주민 수를 의미합니다.

2. 왜 루트 노드의 DP 값을 사용해야 하나?

DFS 탐색은 루트 노드로부터 시작해 자식 노드들의 결과를 부모 노드에 종합하는 과정입니다. 루트 노드가 최종적으로 모든 자식들의 결과를 수합하여 최댓값을 계산하기 때문에, 루트 노드의 DP 값만이 전체 트리에서의 최종 결과를 나타냅니다.

예를 들어, dfs(1)으로 탐색을 했다면:

• 2번 노드는 1번의 자식 중 하나일 뿐이므로, 2번 노드의 DP 값은 2번을 루트로 했을 때의 결과만을 반영합니다. 즉, 2번이 루트인 서브트리 내에서의 최적해를 나타냅니다.
• 따라서 2번 노드의 dp[2][0]과 dp[2][1] 값은 전체 트리의 최적해가 아닙니다.

3. 왜 dp[2]가 전체 트리를 반영하지 못하나?

• 트리 구조에서는 부모 노드가 자식 노드들의 결과를 바탕으로 자신의 DP 값을 계산합니다. 즉, 최종 결과는 부모 노드에서 자식들의 DP 값을 모두 수합한 후에 계산되는 구조입니다.
• 만약 루트 노드를 1번으로 설정했다면, 최종적으로 1번 노드의 DP 값이 모든 서브트리의 결과를 포함하게 됩니다.
• 반대로, 2번 노드는 1번의 서브트리 중 하나이기 때문에, 2번에서 얻을 수 있는 값은 트리 전체가 아닌 2번을 중심으로 한 부분적인 결과만을 포함하고 있습니다.

4. 예시로 설명:

text

코드 복사

1 ├── 2 │ ├── 4 │ └── 5 └── 3 ├── 6 └── 7

• dfs(1)로 시작하면, 1번 마을에서 2번과 3번을 포함한 모든 서브트리 결과가 dp[1][0], dp[1][1]에 저장됩니다.
• 그러나 dfs(1)로 시작한 상태에서 2번 마을의 DP 값(dp[2][0], dp[2][1])을 본다면, 1번과 3번 노드의 정보를 전혀 포함하지 않습니다. 즉, 2번 서브트리 내의 결과만을 포함하고 있기 때문에 전체 트리의 최적해가 될 수 없습니다.

결론:

• 루트 노드의 DP 값이 전체 트리에서의 최종 결과를 나타내며, 루트가 아닌 노드의 DP 값은 그 노드를 중심으로 한 부분 트리의 결과만을 반영합니다.
• 따라서 dfs(1)로 탐색을 시작했다면, 최종 출력은 반드시 **루트 노드인 1번 마을의 DP 값 (dp[1][0], dp[1][1])**을 이용해야 합니다.

이런 이유로, Math.max(dp[2][0], dp[2][1])을 출력하면 트리 전체의 최적해를 구하지 못하게 됩니다.

 

 

의문2 

현재 node가 우수마을이 되지 않았다면, 다음 next 는 우수마을이 되어야만 하는거 아니야? dp[node][0] += Math.max(dp[next][0],dp[next][1])

 

이 부분에 대한 의문을 풀기 위해 문제의 본질과 트리 DP의 동작 방식을 다시 설명하겠습니다. **dp[node][0]**과 **dp[node][1]**의 관계는, 각각의 마을이 우수 마을이 될 때와 되지 않을 때의 최적해를 기록하는 방식입니다. 이제 이 논리가 어떻게 적용되는지 이해해 봅시다.

1. 우수 마을이 될 수 있는 규칙:

• 어떤 마을이 우수 마을이 되면, 그 마을과 연결된 자식 마을은 우수 마을이 될 수 없습니다.
• 반대로, 어떤 마을이 우수 마을이 되지 않았다면, 그 마을과 연결된 자식 마을은 우수 마을이 될 수도 있고, 되지 않을 수도 있습니다.

2. dp[node][0]과 dp[node][1]의 의미:

• dp[node][0]: 현재 node가 우수 마을이 아닌 경우의 최대 주민 수를 나타냅니다. 이 경우 자식 마을들은 자유롭게 우수 마을이 될 수도 있고, 되지 않을 수도 있습니다. 그래서 자식 마을이 우수 마을일 때와 그렇지 않을 때 중 더 큰 값을 선택합니다.
• dp[node][1]: 현재 node가 우수 마을인 경우의 최대 주민 수를 나타냅니다. 이때 자식 마을은 우수 마을이 될 수 없기 때문에, 자식 마을이 우수 마을이 아닌 경우의 값만을 더합니다.

3. 왜 dp[node][0] += Math.max(dp[next][0], dp[next][1])인지:

• dp[node][0]은 현재 노드가 우수 마을이 아닐 때의 최대 주민 수입니다. 즉, 자식 노드(next)가 우수 마을이 될 수도 있고, 되지 않을 수도 있습니다.
• 따라서, 자식 노드가 우수 마을이 될 경우와 되지 않을 경우 중 더 큰 값을 선택하는 것이 최적의 선택입니다. 이 때문에 Math.max(dp[next][0], dp[next][1])으로 더 큰 값을 선택해 부모 노드의 결과에 합산하는 것입니다.

예시로 설명:

text

코드 복사

1 ├── 2 │ ├── 4 │ └── 5 └── 3

• **dp[1][0]**을 계산할 때, 1번 마을이 우수 마을이 아니면 2번과 3번 마을이 우수 마을일 수도 있고, 아닐 수도 있습니다. 따라서:
  • dp[1][0] += Math.max(dp[2][0], dp[2][1]): 2번 마을이 우수 마을일 때와 아닐 때 중 더 큰 값을 선택
  • dp[1][0] += Math.max(dp[3][0], dp[3][1]): 3번 마을이 우수 마을일 때와 아닐 때 중 더 큰 값을 선택

이 과정은, 1번 마을이 우수 마을이 아닐 때 자식 마을들에서 최대로 많은 주민 수를 얻기 위해 자식 마을들이 우수 마을이 될 수 있는지 없는지를 비교하는 방식입니다.

4. dp[node][1]에 대한 처리:

반대로, **dp[node][1] += dp[next][0]**인 이유는, 현재 node가 우수 마을일 때 자식 마을(next)은 우수 마을이 될 수 없기 때문입니다. 따라서 자식 마을의 dp[next][0] (즉, 자식 마을이 우수 마을이 아닐 때의 값)만을 더해야 합니다.

요약:

• dp[node][0] += Math.max(dp[next][0], dp[next][1])은, 부모 노드가 우수 마을이 아니면 자식 노드가 우수 마을이 될 수 있으므로, 자식 노드가 우수 마을일 때와 아닐 때 중 최댓값을 더해주는 것입니다.
• 반면, **dp[node][1] += dp[next][0]**은, 부모 노드가 우수 마을일 때 자식 노드는 우수 마을이 될 수 없기 때문에 자식 노드가 우수 마을이 아닐 때의 값만 더하는 것입니다.

이러한 로직이 트리 구조와 우수 마을의 규칙을 만족시키는 방식입니다.