문제 요약
완전 이진 트리에서 자식 노드의 큐에서 하나씩 올려서, 최종적으로 루트 노드에서 완료한 업무 출력하기
입력형식
- 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);- 트리 순회 & 탐색
트리를 순회하는 기본 방식인 preorder, inorder, postorder는 재귀 함수로 구현할 수 있다.
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;
-
Mechanical Engineering, SKKU