트리를 어떻게 구현해야할지 고민했다..
처음엔 구조체로 접근했다가 삽질하다가 ㅠㅠ
이진트리니까 이차원배열로 풀어도 충분하다고 생각!!
중위순회로 푸는 문제임을 깨닫는데 시간이 걸렸다..!
boj1991(트리순회) 참고!
// 자세히 보면 col 값이 중위순회 순서와 동일하다..
/*
boj2250.cpp
2021-01-08
트리의 높이와 너비
*/
#include <bits/stdc++.h>
using namespace std;
int tree[10001][2] = { 0, };
bool rootNode[10001];
int col = 0;
int row = 0;
vector <int> loc[10001];
vector <pair<int,int>> len;
bool cmp(const pair<int, int>& a, const pair<int, int>& b)
{
return a.second > b.second;
}
void inorder(int k, int row) {
if (k == -1) return;
inorder(tree[k][0],row+1);
col++;
loc[row].push_back(col);
inorder(tree[k][1],row+1);
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int n; cin >> n;
fill_n(rootNode, n + 1, true);
for (int i = 0; i < n; i++) {
int root, left, right; cin >> root >> left >> right;
tree[root][0] = left; tree[root][1] = right;
if(left != -1)
rootNode[left] = false;
if(right != -1)
rootNode[right] = false;
}
int root = 0;
for (int i = 1; i <= n; i++) {
if (rootNode[i]) {
root = i;
break;
}
}
inorder(root, 1);
int row = 1;
while (loc[row].size()) {
int min = loc[row][0];
int max = loc[row][loc[row].size() - 1];
len.push_back({ row,max - min + 1 });
row++;
}
sort(len.begin(), len.end(),cmp);
cout << len[0].first << " " << len[0].second;
}
queue 사용 -> [edited] vector 에도 front / back이 있다고 한다..!
[STL] vector 벡터 정리 및 예제 참고!
vector pair 없애고 for 문 돌려주면서 그 때 그 때 정답 갱신
/*
boj2250.cpp
2021-01-08 정설희
트리의 높이와 너비
*/
#include <bits/stdc++.h>
using namespace std;
int tree[10001][2] = { 0, };
bool rootNode[10001];
int col = 0;
int row = 0;
queue <int> q[10001];
void inorder(int k, int row) {
if (k == -1) return;
inorder(tree[k][0],row+1);
col++;
q[row].push(col);
inorder(tree[k][1],row+1);
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int n; cin >> n;
fill_n(rootNode, n + 1, true);
for (int i = 0; i < n; i++) {
int root, left, right; cin >> root >> left >> right;
tree[root][0] = left; tree[root][1] = right;
if(left != -1)
rootNode[left] = false;
if(right != -1)
rootNode[right] = false;
}
int root = 0;
for (int i = 1; i <= n; i++) {
if (rootNode[i]) {
root = i;
break;
}
}
inorder(root, 1);
int ans1 = 1;
int ans2 = q[1].front()-q[1].back()+1;
int row = 2;
while (!q[row].empty()) {
int min = q[row].front();
int max = q[row].back();
int tmp = max - min + 1;
if (tmp > ans2) {
ans1 = row; ans2 = tmp;
}
row++;
}
cout << ans1 << " " << ans2;
}
트리 문제 풀 때 DFS / BFS / 순회는 꼭 떠올리기
vector<pair<int,int>>v;
소트 방법
< : 오름차순
> : 내림차순
sort(v.begin(),v.end(),cmp)
first 기준
bool cmp(const pair<int, int> &a, const pair<int, int> &b)
{
return a.first < b.first;
}
second 기준
bool cmp(const pair<int, int> &a, const pair<int, int> &b)
{
return a.second < b.second;
}
bool arr[5] = {false};
: false로 초기화
-> 이 방법으로는 true로 초기화 할 수 없다.
<input>
bool arr1[5] = { true }; bool arr2[5] = { false }; for (int i = 0; i < 5; i++) cout << arr1[i] << " "; cout << "\n"; for (int i = 0; i < 5; i++) cout << arr2[i] << " ";
<output>
1 0 0 0 0
0 0 0 0 0
fill_n(arr, n, true);
: true로 초기화