๋ฌธ์
2250๋ฒ: ํธ๋ฆฌ์ ๋์ด์ ๋๋น
์ฒซ์งธ ์ค์ ๋ ธ๋์ ๊ฐ์๋ฅผ ๋ํ๋ด๋ ์ ์ N(1 ≤ N ≤ 10,000)์ด ์ฃผ์ด์ง๋ค. ๋ค์ N๊ฐ์ ์ค์๋ ๊ฐ ์ค๋ง๋ค ๋ ธ๋ ๋ฒํธ์ ํด๋น ๋ ธ๋์ ์ผ์ชฝ ์์ ๋ ธ๋์ ์ค๋ฅธ์ชฝ ์์ ๋ ธ๋์ ๋ฒํธ๊ฐ ์์๋๋ก ์ฃผ์ด์ง๋ค.
www.acmicpc.net
์ฝ๋
#include <iostream>
#include <vector>
#include <unordered_map>
#include <algorithm>
using namespace std;
vector<pair<int,int>>graph[10001];
unordered_map<int,int> cnt;
vector<int> height_arr[10001];
int N, root;
int col[10001];
int seq = 1;
int height = 1;
void inorder(int node){
for(auto next: graph[node]){
if(next.first != -1){
height++;
inorder(next.first);
height--;
}
height_arr[height].push_back(node);
col[node] = seq++;
if(next.second !=-1){
height++;
inorder(next.second);
height--;
}
}
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
cin>>N;
for(int i=0; i<N; i++){
int node, first, second;
cin>>node>>first>>second;
graph[node].push_back({first,second});
cnt[node]++;
cnt[first]++;
cnt[second]++;
}
for(auto it = cnt.begin(); it!=cnt.end(); it++){
if(it->second == 1){
root = it->first;
break;
}
}
inorder(root);
int ans_height = 0, ans_width = 0;
for(int i=0; i<=N; i++){
if(height_arr[i].empty()) continue;
int width = col[height_arr[i].back()] - col[height_arr[i].front()] + 1;
int height = i;
if(width>ans_width){
ans_width = width;
ans_height = height;
}
}
cout<<ans_height << ' '<<ans_width;
}
ํ์ด
์ด์งํธ๋ฆฌ ํ์ ์ดํ๋ฒ
์ด์งํธ๋ฆฌ(Binary Tree) ๋ถ๋ชจ์ ์์์ผ๋ก ๋๋์ด ์๋ ํธ๋ฆฌ ๊ทธ๋ํ ๋ ธ๋์ ์ต๋ ์ฐจ์๊ฐ 2์ด๋ฉฐ, ๊ฐ๊ฐ ์ผ์ชฝ ์์(left child), ์ ์ค๋ฅธ์ชฝ ์์(right child)์ผ๋ก ๋๋ฉ๋๋ค. ์ด์งํธ๋ฆฌ์ ์ํ ์ด์งํธ๋ฆฌ์ ์ํ์
dkswnkk.tistory.com
๋ฌธ์ ์ค๋ช ์ ์ด๋ฏธ์ง๋ฅผ ์ ๋ณด๋ฉด ์ธ๋ก์ด์ ๊น์ด, ๊ฐ๋ก ์ด์ ์ค์ ์ํ(inorder)์ ์์์ธ ๊ฒ์ ์ ์ ์์ต๋๋ค.
- ๋ฃจํธ ๋ ธ๋์ ๊ฒฝ์ฐ๋ ๋จ ํ ๋ฒ๋ง ์ ๋ ฅ๊ฐ์ผ๋ก ๋ค์ด์จ ๋ ธ๋๊ฐ ๋ฃจํธ ๋ ธ๋์ ๋๋ค.
- ๊ทธ ํ ๊ฐ ์ค์ ์ํ ๋ฐฉ์์ผ๋ก ํธ๋ฆฌ๋ฅผ ์ํํ์ฌ ๊ฐ ๋ ธ๋๋ง๋ค ๊ฐ๋ก ์ด์ ์์น(๋๋น)์ ์ธ๋ก์ด์ ์์น(๊น์ด)๋ฅผ ์ ์ฅํด์ค๋๋ค.
- ๊ทธ ํ, ๋์ด๋งํผ ๋ฃจํ๋ฅผ ๋์ ๊ฐ์ฅ ๊ธด ๋๋น๋ฅผ ์ฐพ์์ ์ถ๋ ฅํ๋ฉด ๋ฉ๋๋ค.
'Algorithm ๐ง๐ปโ๐ป > ๋ฐฑ์ค(BOJ)' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
[๋ฐฑ์ค,c++] 1595๋ฒ - ๋ถ์ชฝ๋๋ผ์ ๋๋ก (0) | 2022.08.15 |
---|---|
[๋ฐฑ์ค,c++] 14267๋ฒ - ํ์ฌ ๋ฌธํ1 (0) | 2022.08.15 |
[๋ฐฑ์ค,c++] 19542๋ฒ - ์ ๋จ์ง ๋๋ฆฌ๊ธฐ (0) | 2022.08.14 |
[๋ฐฑ์ค,c++] 19637๋ฒ - IF๋ฌธ ์ข ๋์ ์จ์ค (0) | 2022.08.02 |
[๋ฐฑ์ค,c++] 2812๋ฒ - ํฌ๊ฒ ๋ง๋ค๊ธฐ (0) | 2022.07.29 |
[๋ฐฑ์ค,c++] 13164๋ฒ - ํ๋ณต ์ ์น์ (0) | 2022.07.27 |
๋๊ธ