문제 개요
이진 트리가 하나 주어져 있다고 가정해 봅시다. 우리가 해야 할 작업은 수직 순회(vertical order traversal)를 수행했을 때, 각 수직 라인(열)에 속한 노드 값들의 합을 계산하고, 그중 최댓값을 출력하는 것입니다.
예를 들어 아래와 같은 이진 트리가 있다고 하겠습니다.
이 트리를 수직 순회하면 각 열의 노드 합은 다음과 같습니다.
4 2 1 + 5 + 6 = 12 3 + 8 = 11 7 9
여기서 가장 큰 값은 12입니다. 접근 방법은 생각보다 단순합니다. 먼저 수직 순회를 수행하여 각 열별 노드 값을 모은 뒤, 열별 합을 구하고 그중 최댓값을 찾으면 됩니다.
알고리즘 접근 방식
수직 순회는 일반적으로 너비 우선 탐색(BFS)과 수평 거리(horizontal distance) 개념을 활용해 구현합니다.
- 루트 노드의 수평 거리는 0으로 설정합니다.
- 어떤 노드의 왼쪽 자식은 부모보다 수평 거리가 1 작고(hd − 1), 오른쪽 자식은 1 큽니다(hd + 1).
- 큐에는 노드 포인터와 해당 노드의 수평 거리를 함께 저장합니다.
map<int, vector<int>>자료구조를 사용하면 같은 수평 거리를 가진 노드들이 자동으로 한 그룹으로 묶이며, 맵은 키를 오름차순으로 정렬하므로 왼쪽 열부터 오른쪽 열까지 순서대로 처리할 수 있습니다.
순회가 끝나면 맵의 각 키(열)에 대해 벡터에 담긴 노드 값들을 모두 더하고, 지금까지의 최댓값과 비교하여 더 큰 값으로 갱신합니다.
예제 코드
#include<iostream>
#include<map>
#include<vector>
#include<queue>
using namespace std;
class Node {
public:
int key;
Node *left, *right;
};
Node* getNode(int key){
Node* node = new Node;
node->key = key;
node->left = node->right = NULL;
return node;
}
int getMaxSum(Node* root) {
if (!root)
return -1;
int n = 0;
int k_node = -1;
map<int, vector<int> > current_map;
int hd = 0;
queue<pair<Node*, int> > que;
que.push(make_pair(root, hd));
while (!que.empty()) {
pair<Node*, int> temp = que.front();
que.pop();
hd = temp.second;
Node* node = temp.first;
current_map[hd].push_back(node->key);
if (node->left != NULL)
que.push(make_pair(node->left, hd - 1));
if (node->right != NULL)
que.push(make_pair(node->right, hd + 1));
}
map<int, vector<int> >::iterator it;
int maximum = INT_MIN;
for (it = current_map.begin(); it != current_map.end(); it++) {
int temp_sum = 0;
for (int i = 0; i < it->second.size(); ++i) {
temp_sum += it->second[i];
}
if(maximum < temp_sum){
maximum = temp_sum;
}
}
return maximum;
}
int main() {
Node* root = getNode(1);
root->left = getNode(2);
root->right = getNode(3);
root->left->left = getNode(4);
root->left->right = getNode(5);
root->right->left = getNode(6);
root->right->right = getNode(7);
root->right->left->right = getNode(8);
root->right->right->right = getNode(9);
cout << "Maximum sum of vertical nodes: " << getMaxSum(root);
}실행 결과
Maximum sum of vertical nodes: 12
코드 설명 및 복잡도 분석
getMaxSum() 함수는 다음과 같은 흐름으로 동작합니다.
- 루트가
NULL인 경우 −1을 반환하여 빈 트리를 처리합니다. - BFS를 위해 큐에 (노드, 수평 거리) 쌍을 넣고, 큐가 빌 때까지 반복합니다.
- 큐에서 꺼낸 노드의 키 값을 현재 수평 거리에 해당하는 맵의 벡터에 추가합니다.
- 왼쪽 자식은 hd − 1, 오른쪽 자식은 hd + 1로 설정하여 큐에 삽입합니다.
- 순회가 끝나면 각 열의 합을 계산해 최댓값을 구해 반환합니다.
시간 복잡도는 트리의 노드 수를 N이라 할 때 O(N log N)입니다. BFS 순회 자체는 O(N)이지만, 맵에 삽입할 때마다 정렬된 위치를 찾는 데 로그 시간이 소요되기 때문입니다. 공간 복잡도 역시 모든 노드를 맵에 저장하므로 O(N)입니다.
만약 열의 순서가 중요하지 않다면 unordered_map을 사용해 평균적으로 O(N)까지 성능을 개선할 수 있습니다.