백준 25515번 트리 노드 합의 최대값

문제 설명

이번 문제는 트리가 주어지고 노드마다 하나의 정수가 적혀있을 때, 루트 노드에서 시작해 이웃한 노드를 방문하여 방문한 노드에 적혀있는 정수 합의 최대값을 출력하는 문제입니다.

 

문제 풀이

아이디어

각 노드에서 연결된 서브 트리에서의 최대값 찾기

루트 노드로부터 트리의 형태가 주어졌으므로, 루트노드와 연결된 각 서브트리에서 노드의 정수값을 더했을 때의 최대값을 구해줍니다.

한 노드에서 자신의 자식으로부터 얻어진 정수의 최대값을 알면 해당 서브트리에서 정수 합의 최대값을 구할 수 있습니다.

그러므로, 각 노드마다 자식으로부터 얻어진 정수합의 최대값과 자신의 정수값과의 합이 최대가되도록 해줍니다.

 

풀이

서브트리 정수합의 최대값 구하기

재귀를 이용하여 각 노드의 자식 노드를 탐색합니다.

각 노드가 leaf 노드에 도달했을 경우, 자신의 정수값을 반환해줍니다.

각 노드가 자식 노드가 있을 경우, 자식 노드로부터 올라온 정수합의 최대값과 자신의 노드에 적힌 정수를 합하여 만들 수 있는 최대값을 반환해줍니다. (만약 정수합의 최대값이 음수라면, 부모 노드의 최대값 형성에 도움이 되지 않으므로 0을 반환합니다)

이를 반복하면, 루트노드에서는 자식노드로부터 올라온 최대값을 알 수 있으므로, 루트노드의 정수값을 더해 전체 트리의 정수합의 최대값을 구할 수 있습니다.

 

 

해결

이번 문제는 각 노드에서 자식 노드로부터 올라오는 값을 정해준다면 쉽게 풀 수 있었던 문제입니다.

 

문제 링크 : https://www.acmicpc.net/problem/25515

25515번: 트리 노드 합의 최댓값

코드 링크 : https://github.com/beomseok37/baekjoon/blob/master/new!/25515.py