[Algorithm]Baekjoon 1949번 : 우수 마을

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

1949번: 우수 마을

#include <iostream>
#include <string>
#include <map>
#include <vector>
#include <algorithm>
#include <math.h>
#include <queue>
#include <functional>
#include <sstream>
#include <memory.h>
#include <deque>
#include <set>
#include <unordered_map>
#include <stack>
#include <numeric>
 
using namespace std;
 
 
int n;
int citizensArr[10001] = { 0 };
vector<vector<int>> graph(10001);
bool visited[10001] = { false };
int dp[10001][2] = { 0 };
 
void DFS(int node)
{
    visited[node] = true;
 
    dp[node][0] = 0;
    dp[node][1] = citizensArr[node];
 
    for (int i = 0; i < graph[node].size(); ++i)
    {
        int nextNode = graph[node][i];
 
        if (visited[nextNode]) continue;
 
        DFS(nextNode);
 
        dp[node][0] += max(dp[nextNode][0], dp[nextNode][1]);
        dp[node][1] += dp[nextNode][0]; // 현재 우수마을 아니면, 다음껀 반드시 우수마을이여함.
    }
}
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    cin >> n;
 
    for (int i = 1; i <= n; ++i)
    {
        cin >> citizensArr[i];
 
        dp[i][0] = dp[i][1] = -1;
    }
 
    for (int i = 0; i < n - 1; ++i)
    {
        int a, b;
        cin >> a >> b;
        graph[a].push_back(b);
        graph[b].push_back(a);
    }
 
    DFS(1);
 
    cout << max(dp[1][0], dp[1][1]);
}

 

이거의 약간 하위호환 문제는 풀었던거같은데 (사회망 서비스) 이거는 쉽게 풀지 못했다.

다른 사람들풀이를 보니까 거의 공통된풀이인데, 처음에 잘 이해가 안갔던것은 41번째라인이다.

현재마을이 우수마을이 아니라면 다음마을이 우수든 아니든 최대값을 누적시키는 것이다.

 

대충 보아하니 최댓값을 구하는거라서 절대 우수x->우수x->우수x  형태가 되어지지 않는다는 것이다.

그래서 테스트케이스를 노트에다가 끄적이니까 얼추 그림이 그려지긴 한다.

 

위 코드를 기준으로, 어떤 노드의 자식노드들이 리프노드라 가정해보자.

이 자식노드들을 다 합친값이, 현재노드값보다 더 크다면 현재노드의 부모노드 dp[부모][0]과 dp[부모][1]에 자식리프노드들을 다 합친값이 누적될 것이다. 현재노드값은 dp[부모][0]에만 갱신될 것이다. 현재노드를 우수마을로 선정하면 상위노드는 반드시 우수마을이 아니여야하니까

그러면 dp[부모][0]과 dp[부모][1]에는 리프노드들합친값이 누적되어있는데, 이걸 다시 상위노드로 리턴한다하면 당연히 dp[부모][1]의 값이 리턴된다.

왜? 리프노드합친값 + 부모의값을 리턴하니까. dp[부모][0]은 그냥 리프노드합친값만 리턴하는데, 당연히 부모값을 합친거까지 리턴하는게 이득이다. 즉, 결국 반드시 부모는 우수마을로 선정하게 된다.

이런 표현이 max비교하는 과정에서 표현되어지는 것이다. 자연히 걸러지게 된다.

 

물론 이 케이스만으론 부족하고 반대의 케이스를 생각해보자.

맨 하단으로 내려가서, 자식리프노드들을 다 합친값이 현재노드보다 '작다'고 생각해보자. 

그러면 현재노드[0]에는 자식노드들을 합친값이 들어있게되고 현재노드[1]에는 자기자신값이 들어가있게 된다.

이 상태에서 상위노드로 다시 리턴되면, 상위노드[0]에는 max(자식노드들합친값, 현재노드값)이 들어가게 되고

상위노드[1]에는 상위노드값 + 자식노드들합친값이 들어가 있게 된다.

 

상위노드[0]에 자식리프노드들값 합쳐진게 들어간다면, 자식리프노드마을들이 우수마을 o, 현재마을은 우수x, 상위마을 우수x가 된다.

상위노드[0]에 현재노드값이 들어간다면, 자식리프노드마을들은 우수x, 현재우수마을o, 상위마을우수x가 된다.

 

이런식으로 반복되기 떄문에 로직상 우수x가 연달아 세번이 나올수가 없다.

이건 말로 설명하기가 쉽지않은데, 코드가 쉬우니까 직접 노트에 끄적여보는걸 추천한다.