C++로 해결하는 경로 합 IV(Path Sum IV): 루트-리프 경로 합 구하기

깊이가 5보다 작은 이진 트리를 정수 리스트로 표현한다고 가정해 보겠습니다. 트리의 깊이가 5 미만이라면, 이 트리는 세 자리 정수들의 리스트로 나타낼 수 있습니다. 리스트에 포함된 각 정수는 다음과 같은 정보를 담고 있습니다.

백의 자리 숫자: 해당 노드의 깊이(D)를 나타내며, 1 ≤ D ≤ 4 범위를 가집니다.
십의 자리 숫자: 노드가 속한 레벨에서의 위치(P)를 나타내며, 범위는 1~8입니다. 이 위치는 완전 이진 트리에서의 위치와 동일합니다.
일의 자리 숫자: 노드의 값(V)을 나타내며, 0 ≤ V ≤ 9 범위를 가집니다.

우리가 구해야 할 것은 루트에서 리프 노드까지 이어지는 모든 경로의 합입니다.

예를 들어 입력이 [113, 215, 221]이라면 출력은 12가 됩니다. 이 리스트가 표현하는 트리는 다음과 같습니다.

경로 합은 (3 + 5) + (3 + 1) = 12입니다.

해결 접근 방법

이 문제는 DFS(깊이 우선 탐색)를 활용하여 해결할 수 있습니다. 단계별로 살펴보겠습니다.

정수 쌍(pair)을 저장할 맵(graph)을 하나 정의합니다.
dfs() 함수를 정의합니다. 이 함수는 node, level, pos, sum(기본값 0)을 매개변수로 받습니다.
isLeaf를 true로 초기화합니다.
i를 0부터 graph[level + 1]의 크기 미만까지 1씩 증가시키며 반복합니다.
- temp를 graph[level + 1][i]로 설정합니다.
- temp.first / 2가 pos와 같다면:
  - isLeaf를 false로 갱신합니다.
  - dfs(temp.second, level + 1, temp.first, sum + node)를 재귀 호출합니다.
isLeaf가 참이라면, 즉 리프 노드라면 ret에 (sum + node)를 더합니다.

메인 메서드 처리 과정

ret을 0으로 초기화합니다.
nums의 모든 요소에 대해 다음을 수행합니다.
- x := nums[i]
- val := x mod 10 (일의 자리 추출)
- x := x / 10
- pos := x mod 10 (십의 자리 추출)
- x := x / 10
- level := x (백의 자리 추출)
- graph[level]의 끝에 { (1 << (level - 1)) + pos - 1, val }을 삽입합니다.
dfs(graph[1][0].second, 1, graph[1][0].first)를 호출합니다.
ret을 반환합니다.

C++ 구현 예제

아래 구현을 통해 더 잘 이해해 보겠습니다.

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
   int ret;
   map <int, vector < pair <int, int> > > graph;
   void dfs(int node, int level, int pos, int sum = 0){
      bool isLeaf = true;
      for (int i = 0; i < graph[level + 1].size(); i++) {
         pair<int, int> temp = graph[level + 1][i];
         if (temp.first / 2 == pos) {
            isLeaf = false;
            dfs(temp.second, level + 1, temp.first, sum + node);
         }
      }
      if (isLeaf) {
         ret += (sum + node);
      }
   }
   int pathSum(vector<int>& nums) {
      ret = 0;
      for (int i = 0; i < nums.size(); i++) {
         int x = nums[i];
         int val = x % 10;
         x /= 10;
         int pos = x % 10;
         x /= 10;
         int level = x;
         graph[level].push_back({ (1 << (level - 1)) + pos - 1, val });
      }
      dfs(graph[1][0].second, 1, graph[1][0].first);
      return ret;
   }
};
main(){
   Solution ob;
   vector<int> v = {113,215,221};
   cout<<(ob.pathSum(v));
}

동작 원리

이 알고리즘의 핵심은 각 노드의 위치를 고유한 정수로 인코딩하는 데 있습니다. (1 << (level - 1)) + pos - 1 공식으로 계산된 위치 값은 힙(heap) 인덱싱과 유사하게 동작하여, 어떤 자식 노드의 인코딩 값을 2로 나누면 부모 노드의 인코딩 값이 됩니다. 따라서 dfs() 함수에서 temp.first / 2 == pos 조건을 확인함으로써 현재 노드의 실제 자식 여부를 판별할 수 있으며, 더 이상 자식이 없는 노드(리프)에 도달했을 때 지금까지 누적된 경로 합을 최종 결과에 더하게 됩니다.

입력

{113,215,221}