[백준 1949번] 우수 마을 (java)

1949번: 우수 마을

 

트리에서 다이나믹 프로그래밍을 이용하여 푸는 문제다.

dfs방식으로 루트노드에서부터 리프노드까지 top - down 으로 내려간 후, 다시 리프노드에서부터 위로 올라가면서 dp배열을 업데이트한다.

 

dp배열은 이차원 배열로 생성하여서 n번 마을이 우수 마을인 경우와 그렇지 않은 경우로 나누었다.

 

• dp[n][0] : n번 마을이 우수 마을이 아닐 때, n번 마을을 루트노드로 하는 하위트리의 마을 주민 수의 총합
• dp[n][1] : n번 마을이 우수 마을일 때, n번 마을을 루트노드로 하는 하위트리의 마을 주민 수의 총합

 

아래 그림을 보자.

만약 n번 마을이 우수 마을이라면(dp[n][1]), 자식 마을은 모두 우수 마을이어서는 안된다.

그러므로 l번 마을이 우수 마을이 아닐 때의 마을 주민 수의 총합(dp[l][0])과, r번 마을이 우수 마을이 아닐 때의 마을 줌니 수의 총합(dp[r][0])을 더한 결과가 dp[n][1]가 된다.

(아래 그림의 빨간색 노드는 우수 마을로 선정되었음을 의미)

 

n번 마을이 우수 마을 아닌 경우, 자식 노드가 m개 있다고 할 때, 최대 마을 주민 수의 총합은 다음과 같이 구할 수 있다.

 

dp[n][1] = dp[자식노드1][0] + dp[자식노드2][0] + ... + dp[자식노드m][0]

 

 

만약 n번 마을이 우수 마을이 아니라면(dp[n][0]), 자식 마을은 우수 마을일 수도 있고 아닐 수도 있다.

따라서 n번 마을이 우수 마을이 아닐 때 최대가 되는 마을 주민 수의 총합은 다음과 같이 3가지 경우가 있다. (여기서는 자식 노드가 2개뿐이므로 총 3가지 경우가 생기는 것이다.)

이 3가지 중에서 가장 큰 값이 dp[n][0]에 들어가게 된다.

 

 

n번 마을이 우수 마을 아닌 경우, 자식 노드가 m개 있다고 할 때, 최대 마을 주민 수의 총합은 다음과 같이 구할 수 있다.

 

dp[n][0] = Math.max(dp[자식노드1][0], dp[자식노드1][1]) 

               + Math.max(dp[자식노드2][0], dp[자식노드2][1]) 

               + ...

               + Math.max(dp[자식노드m][0], dp[자식노드m][1])

               + n번 마을의 주민 수

 

---

 

트리의 아래에서 위로 올라오면서 계속 dp[n][0]와 dp[n][1]을 구한다.

이 때 트리의 루트노드는 아무 마을로 선택해도 결과는 동일하다.

문제에서 주어진 예제의 경우, 1번 마을을 루트노드로 잡으면 다음과 같은 트리 모양이 될 것이다.

 

 

 

아래에서 위로 올라오면서 점화식을 만족하면서 dp[n][0], dp[n][1]를 갱신한다.

루트노드까지 올라오고 나면, 각각의 마을마다 다음과 같은 dp배열 정보를 갖는다.

 

 

 

마지막으로 dp[1][0]와 dp[1][1]을 비교하여 더 큰 값이 최종 마을 주민 수의 최대값이 된다.

 

소스코드 :