문제
이진 트리에서 임의의 두 정점의 공통 조상 중 가장 가까운 것을 찾으려 한다.
예를 들어, 아래의 이진 트리에서 정점 8과 13의 공통 조상은 정점 3와 1 두 개가 있다.
이 중 8, 13에 가장 가까운 것은 정점 3이다.
정점 3을 루트로 하는 서브 트리의 크기(서브 트리에 포함된 정점의 수)는 8이다.
임의의 이진 트리가 주어지고, 두 정점이 명시될 때 이들의 공통 조상 중 이들에 가장 가까운 정점을 찾고, 그 정점을 루트로 하는 서브 트리의 크기를 알아내는 프로그램을 작성하라.
입력에서 주어지는 두 정점이 서로 조상과 자손 관계인 경우는 없다.
위의 트리에서 예를 든다면 두 정점이 “11과 3”과 같이 주어지는 경우는 없다.
[입력]
가장 첫줄은 전체 테스트케이스의 수이다.
10개의 테스트 케이스가 주어진다.
두 줄이 하나의 테스트 케이스가 되며, 따라서 전체 입력은 20줄로 이루어진다.
각 케이스의 첫줄에는 트리의 정점의 총 수 V와 간선의 총 수 E, 공통 조상을 찾는 두 개의 정점 번호가 주어진다 (정점의 수 V는 10 ≤ V ≤ 10000 이다).
그 다음 줄에는 E개 간선이 나열된다. 간선은 간선을 이루는 두 정점으로, 항상 “부모 자식” 순서로 표기된다.
위에서 예로 든 트리에서 정점 5와 8을 잇는 간선은 “5 8”로 표기되고, 절대로 “8 5”와 같이 표기되지는 않는다.
간선이 입력되는 순서는 정해져 있지 않다. 입력에서 이웃한 수는 모두 공백으로 구분된다.
정점의 번호는 1부터 V까지의 정수이며, 전체 트리에서 루트가 되는 정점은 항상 1번으로 표기된다.
부모 정점이 자식 정점보다 항상 번호가 작은 것은 아니다. 즉, 40번 정점이 20번 정점의 부모가 될 수도 있다.
이 문제에서 자식 정점이 부모 정점의 왼쪽 자식인지 오른쪽 자식인지는 중요하지 않다.
[출력]
총 10줄에 10개의 테스트 케이스 각각에 대한 답을 출력한다.
각 줄은 테스트 케이스의 번호를 의미하는 ‘#x’로 시작하고 공백을 하나 둔 다음 답을 기록한다.
답은 공통조상 중 가장 가까운 것의 번호, 그것을 루트로 하는 서브 트리의 크기를 뜻하는 2개의 정수로 구성된다. 이 두 정수는 공백으로 구분한다.
코드
#include <iostream>
using namespace std;
struct node {
int data;
node* left;
node* right;
node* par;
};
constexpr size_t MAX = 10000;
node* r_find;
int node_count = 0;
int c_f = 0;
int cnt = 0;
void find_parent(node* cur,int c)
{
if (cur!= 0)
{
find_parent(cur->left, c);
if (cur->data == c)
{
r_find = cur;
}
find_parent(cur->right, c);
}
}
void postorder(node* cur)
{
if (cur!=0)
{
postorder(cur->left);
cnt++;
postorder(cur->right);
}
}
int main()
{
int n, v, e, child1, child2,line1,line2;
cin >> n;
for (int i = 0; i < n; i++)
{
node node_pool[MAX] = { 0, };
cin >> v >> e >> child1 >> child2;
for (int q = 0; q < e; q++)
{
cin >> line1 >> line2;
if (node_pool[line1 - 1].left==0)
{
node_pool[line1 - 1].data = line1;
node_pool[line2 - 1].data = line2;
node_pool[line1 - 1].left = &node_pool[line2 - 1];
node_pool[line2 - 1].par = &node_pool[line1 - 1];
}
else if (node_pool[line1 - 1].right == 0)
{
node_pool[line2 - 1].data = line2;
node_pool[line1 - 1].right = &node_pool[line2 - 1];
node_pool[line2 - 1].par = &node_pool[line1 - 1];
}
}
find_parent(&node_pool[0], child1);
node* find1 = r_find;
find_parent(&node_pool[0], child2);
node* find2 = r_find;
int flag = 0;
int cnt1 = 0;
int cnt2 = 0;
while (find1->par!=0)
{
node* temp2 = find2;
while (temp2->par != 0)
{
if (find1->par == temp2->par)
{
flag = 1;
break;
}
temp2 = temp2->par;
}
if (flag == 1)
{
break;
}
find1 = find1->par;
}
postorder(find1->par);
cout << "#" << i + 1 << ' ' << find1->par->data << ' ' << cnt << endl;
cnt = 0;
node_count = 0;
}
return 0;
}설명
처음 문제를 봤을 때 순회를 이용하여 푸는 방법을 고민하였다.
하지만 해결할 수 없었고 어쩔 수 없이 다른 해결법들을 찾아보았다.
단순히 순회만 이용해서는 안되고 DFS를 같이 병행하여 풀었어야했다.
후기
추후에 복습을 다시 하고 넘어가야겠다.
알고리즘 쉽지않다..
