완전 이진 트리에서 자식 노드의 큐에서 하나씩 올려서, 최종적으로 루트 노드에서 완료한 업무 출력하기
- 1 ≤ H ≤ 10
1 ≤ K ≤ 10
1 ≤ R ≤ 1,000- 첫 줄에 조직도의 높이 H, 말단에 대기하는 업무의 개수 K, 업무가 진행되는 날짜 수 R이 주어진다.
- 그 다음 줄부터 각각의 말단 직원에 대해 대기하는 업무가 순서대로 주어진다.
- 제일 왼쪽의 말단 직원부터 순서대로 주어진다.
- 완료된 업무들의 번호 합을 정수로 출력한다.
H
를 입력받아 루트 노드를 생성하고, 레벨 순회하며 자식 노드를 생성한다. h
가 1까지 내려왔을 때는, 말단 노드의 큐를 입력받는다.day
을 선언하고, 1부터 R
까지 반복하며 트리의 상태를 업데이트한다.h = 0
: 말단 노드이므로, skiph = 1
: 말단 left and right 노드의 큐에서 업무를 가져온다.h < H
: 날짜에 따라 left or right 노드에서 업무를 가져온다.h = H
: 날짜에 따라 일을 처리하고, left or right 노드에서 업무를 가져온다.0
: 노드 구조 생성class Node {
public:
int work;
int height;
deque<int> q_left;
deque<int> q_right;
deque<int> q;
Node* left;
Node* right;
Node* parent;
Node(int _work, int _height) {
work = _work;
height = _height;
}
};
1
: 트리 생성 & 말단 노드의 큐 입력 받기void new_workers(Node* m) {
queue<Node*> q;
q.push(m);
Node* tmp;
int new_work = 0;
while (!q.empty()) {
tmp = q.front();
q.pop();
// 현재 노드가 말단이면,
if (tmp->height == 0) {
for (int i=0; i<K; i++) {
cin >> new_work;
if (new_work != 0)
tmp->q.push_back(new_work);
new_work = 0;
}
cout << endl;
continue;
}
if (tmp->left == NULL) {
tmp->left = new Node(0, tmp->height-1);
tmp->left->parent = tmp;
q.push(tmp->left);
}
if (tmp->right == NULL) {
tmp->right = new Node(0, tmp->height-1);
tmp->right->parent = tmp;
q.push(tmp->right);
}
}
}
2
: 날짜만큼 반복 // 날짜 동안 반복
for (day=1; day<=R; day++) {
UpdateTree(head, day);
}
cout << head->work << endl;
3
: 트리를 레벨 순회하면서, 높이 별로 해야 할 행동 수행void UpdateTree(Node* m, int day) {
deque<Node*> q;
q.push_front(m);
Node* tmp;
int curr_work;
// deque에 순서대로 삽입
while (!q.empty()) {
tmp = q.front();
q.pop_front();
// 말단일 때, skip
if (tmp->height == 0) {
}
// h == 1일 때, 아래에서 땡겨오기만 함
else if (tmp->height == 1) {
// H == 1일 경우, 일처리
if (H == 1) {
// 홀수 날이면, 왼쪽 처리
if (day % 2 == 1) {
if (!tmp->q_left.empty()) {
// work에 더하기
tmp->work += tmp->q_left.front();
tmp->q_left.pop_front();
}
}
// 짝수 날이면, 오른쪽 처리
else {
if (!tmp->q_right.empty()) {
// work에 더하기
tmp->work += tmp->q_right.front();
tmp->q_right.pop_front();
}
}
}
if (!tmp->left->q.empty()) {
tmp->q_left.push_back(tmp->left->q.front());
tmp->left->q.pop_front();
}
if (!tmp->right->q.empty()) {
tmp->q_right.push_back(tmp->right->q.front());
tmp->right->q.pop_front();
}
}
// h <= H일 때, 날짜에 따라 left or right에서 땡겨옴
else if (tmp->height <= H) {
// h == H일 때, 먼저 일처리
if (tmp->height == H) {
// 홀수 날이면, 왼쪽 처리
if (day % 2 == 1) {
if (!tmp->q_left.empty()) {
// work에 더하기
tmp->work += tmp->q_left.front();
tmp->q_left.pop_front();
}
}
// 짝수 날이면, 오른쪽 처리
else {
if (!tmp->q_right.empty()) {
// work에 더하기
tmp->work += tmp->q_right.front();
tmp->q_right.pop_front();
}
}
}
if (day % 2 == 1) {
// left, right의 q_left에서 땡겨옴
if (!tmp->left->q_left.empty()) {
tmp->q_left.push_back(tmp->left->q_left.front());
tmp->left->q_left.pop_front();
}
if (!tmp->right->q_left.empty()) {
tmp->q_right.push_back(tmp->right->q_left.front());
tmp->right->q_left.pop_front();
}
}
else {
// left, right의 q_right에서 땡겨옴
if (!tmp->left->q_right.empty()) {
tmp->q_left.push_back(tmp->left->q_right.front());
tmp->left->q_right.pop_front();
}
if (!tmp->right->q_right.empty()) {
tmp->q_right.push_back(tmp->right->q_right.front());
tmp->right->q_right.pop_front();
}
}
}
// 다음 노드로 이동
if (tmp->left) {
q.push_back(tmp->left);
}
if (tmp->right) {
q.push_back(tmp->right);
}
}
}
개인적으로 얻어가는 것이 정말 많았던 문제이다.
class Node {
public:
int work;
int height;
deque<int> q_left;
deque<int> q_right;
deque<int> q;
Node* left;
Node* right;
Node* parent;
Node(int _work, int _height) {
work = _work;
height = _height;
}
};
...
Node* head = new Node(0, H);
void preorder(Node* root) {
if (root == NULL) return;
cout << root->data << "->";
preorder(root->left);
preorder(root->right);
}
void inorder(Node* root) {
if (root == NULL) return;
preorder(root->left);
cout << root->data << "->";
preorder(root->right);
}
void postorder(Node* root) {
if (root == NULL) return;
preorder(root->left);
preorder(root->right);
cout << root->data << "->";
}
또한, 높이 순서대로 순회하고 싶다면 queue를 이용해 BFS하듯 구현하면 된다. 유사코드는 아래와 같다.
void levelorder(Node* n) {
큐 생성
첫 노드 push
노드 포인터 tmp 생성
while (큐가 비어있지 않는 동안) {
맨 앞의 노드를 가져오고
큐 pop
// 여기에 원하는 행동
// 좌, 우 노드 큐에 추가
if (왼쪽 비어있지 않다면)
왼쪽 노드 push
if (오른쪽 비어있지 않다면)
오른쪽 노드 push
}
}
deque
C++에는 queue와 stack의 기능을 동시에 활용할 수 있는 deque
라이브러리가 존재한다.
특히, queue나 stack의 인자를 출력하고 싶을 때 모든 element를 pop해야 하지만, deque
는 전체 element를 순회할 수 있는 포인터인 iterator가 존재하여 매우 편리하다.
DFS, BFS처럼 간단하게 노드 or 그래프 순회하는 경우는 일반 queue를 사용하고, 출력이 필요한 경우 deque를 사용하면 될 듯하다.
push, pop
#include<iostream>
#include<deque>
// queue 사용하기
deque<int> q;
q.push_back(a);
cout << q.front() << endl;
q.pop_front();
// stack 사용하기
deque<int> s;
s.push_front(a);
cout << s.back() << endl;
s.pop_back();
deque의 인자 출력
#include<iostream>
#include<deque>
deque<int>::iterator it;
// queue 출력하기
deque<int> q;
q.push_back(a);
q.push_back(b);
q.push_back(c);
q.push_back(d);
for (it=q.begin(); it!=q.end(); it++)
cout << *(it) << " ";
cout << endl;
// stack 출력하기
deque<int> s;
s.push_front(a);
s.push_front(b);
s.push_front(c);
s.push_front(d);
for (it=s.begin(); it!=s.end(); it++)
cout << *(it) << " ";
cout << endl;