일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | ||||
4 | 5 | 6 | 7 | 8 | 9 | 10 |
11 | 12 | 13 | 14 | 15 | 16 | 17 |
18 | 19 | 20 | 21 | 22 | 23 | 24 |
25 | 26 | 27 | 28 | 29 | 30 | 31 |
Tags
- algoritm
- binary search
- stack
- LEVEL2
- level3
- programmers
- effective C++
- Unity
- SWEA
- Topological Sort
- smart pointer
- 3D RPG
- Bronze
- Silver
- Zenject
- BOJ
- Modern C++
- BFS
- Greedy
- 8-Puzzle
- Gold
- C++11
- Project
- level1
- two pointer
- 프로그래머스
- Euclidean
- algorithm
- knapsack Problem
- trie
Archives
- Today
- Total
Patrick's Devlog
[SWEA/C++] 공통조상(1248번) 본문
1. 문제 개요
https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV15PTkqAPYCFAYD
SW Expert Academy
SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요!
swexpertacademy.com
※ 본 문제는 SW Expert 아카데미의 문제이므로 무단으로 복제 X
1-1. 설명
이진 트리에서 임의의 두 정점 공통 조상 중 가장 가까운 것을 찾으려한다.
위와 같이 임의의 이진트리가 주어지고 두 정점이 명시될 때 이들의 공통조상 중 가장 가까운 정점을 찾고, 그 정점을 루트로하는 서브 트리의 크기를 알아내는 프로그램을 작성해라. 입력에서 주어지는 두 정점이 서로 조상과 자손관계인 경우는 없다.
1-2. 제한 사항
- 첫줄은 전체 테스트케이스의 수, 10개가 주어짐
- 각 케이스의 첫줄은 정점의 수, 간선의 수, 공통 조상을 찾는 두 개의 정점 번호
- 정점의 수는 10 이상 10000 이하
- 그 다음 줄에는 간선 수만큼의 정점이 주어지며, "부모 자식" 순서로 표기
2. 구현
2-1. 풀이
정점을 저장한 Node를 구성해주고, 부모와 각각의 자식을 저장할 수 있게끔 하였다. 간선의 수만큼 for문을 돌려 정점과 그에따른 부모 및 자식을 저장해주고, 각각의 조상을 저장하는 배열을 선언해 저장해준다. 후에 동일한 공통 조상을 for문을 통해 찾고, 찾은 공통 조상을 재귀를 통해 개수를 구해준다.
2-2. 코드
#include <iostream>
#include <string>
#include <algorithm>
#include <cstring>
using namespace std;
constexpr size_t MAX_NODE = 10001;
struct Node {
int key;
Node* left;
Node* right;
Node* parent;
};
void parentSearch1(Node* node);
void parentSearch2(Node* node);
int equalElementSearch();
void countSubTree(Node* node);
Node node_pool[MAX_NODE];
Node* newNode(int x) {
node_pool[x].key = x;
node_pool[x].left = nullptr;
node_pool[x].right = nullptr;
node_pool[x].parent = nullptr;
return &node_pool[x];
}
// 루트 노드를 가리키는 포인터
Node* root;
int parentV1[MAX_NODE], parentV2[MAX_NODE];
int index1 = 0, index2 = 0, countTree = 0;
void init() {
memset(parentV1, 0, sizeof(parentV1));
memset(parentV2, 0, sizeof(parentV2));
memset(node_pool, 0, sizeof(node_pool));
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int T, V ,E ,V1, V2 ,A ,B;
cin >> T;
for (int test_case = 1; test_case <= T; ++test_case) {
init();
cin >> V >> E >> V1 >> V2;
for (int i = 0; i < E; i++) {
cin >> A >> B;
if (node_pool[A].key == NULL) newNode(A); // A 노드 저장
if (node_pool[B].key == NULL) newNode(B); // B 노드 저장
if (node_pool[A].left == nullptr) node_pool[A].left = &node_pool[B]; // 왼쪽 연결
else if (node_pool[A].right == nullptr) node_pool[A].right = &node_pool[B]; // 오른쪽 연결
node_pool[B].parent = &node_pool[A]; // 부모 연결
}
index1 = 0, index2 = 0, countTree = 0;
parentSearch1(&node_pool[V1]); // 첫번째 노드 부모 저장
parentSearch2(&node_pool[V2]); // 두번째 노드 부모 저장
int resultNum = equalElementSearch(); // 가장 가까운 공통 조상 찾기
countSubTree(&node_pool[resultNum]); // 공통 조상을 기준으로 한 SubTree 개수 세기
cout << '#' << test_case << ' ' << resultNum << ' ' << countTree << "\n";
}
}
void parentSearch1(Node* node) {
if (node->key == NULL || node->key == 1) return;
parentV1[index1++] = node->parent->key;
if (node->parent != nullptr) parentSearch1(node->parent);
}
void parentSearch2(Node* node) {
if (node->key == NULL || node->key == 1) return;
parentV2[index2++] = node->parent->key;
if (node->parent != nullptr) parentSearch2(node->parent);
}
int equalElementSearch() {
for (int i = 0; i < index1; i++) {
for (int j = 0; j < index2; j++) {
if (parentV1[i] == parentV2[j]) return parentV1[i];
}
}
return 0;
}
void countSubTree(Node* node) {
countTree += 1;
if (node->left != nullptr) countSubTree(node->left);
if (node->right != nullptr) countSubTree(node->right);
}
'Study > Algorithms Practice' 카테고리의 다른 글
[SWEA/C++] 파핑파핑 지뢰 찾기(1868번) (0) | 2022.08.10 |
---|---|
[SWEA/C++] 자기 방으로 돌아가기(4408번) (0) | 2022.07.26 |
[SWEA/C++] 암호문3(1230번) (0) | 2022.07.20 |
[BOJ/C++] 중복 빼고 정렬하기(10867번) (0) | 2022.07.14 |
[BOJ/C++] 안전 영역(2468번) (0) | 2022.07.12 |