3.1. 15이원준 ¶
#include<iostream> using namespace std; int level[20000][2] = {0, }; int arr[20000][2]; int ex[20000][2] = { 0, }; int myNum[20000] = {0, }; int maxDep = 0; int checkNum(int child){ if(arr[child][0] != -1){ ex[child][0] = checkNum(arr[child][0]); } if(arr[child][1] != -1){ ex[child][1] = checkNum(arr[child][1]); } return ex[child][0] + ex[child][1] + 1; } void fill(int now){ if(arr[now][0] != -1){ myNum[arr[now][0]] = myNum[now] - ex[arr[now][0]][1] - 1; fill(arr[now][0]); } if(arr[now][1] != -1){ myNum[arr[now][1]] = myNum[now] + ex[arr[now][1]][0] + 1; fill(arr[now][1]); } } void answer(int dep, int now){ if(dep > maxDep){ maxDep = dep; } if(arr[now][0] != -1){ if(myNum[arr[now][0]] < level[dep][0]){ level[dep][0] = myNum[arr[now][0]]; } if(myNum[arr[now][0]] > level[dep][1]){ level[dep][1] = myNum[arr[now][0]]; } answer(dep + 1, arr[now][0]); } if(arr[now][1] != -1){ if(myNum[arr[now][1]] < level[dep][0]){ level[dep][0] = myNum[arr[now][1]]; } if(myNum[arr[now][1]] > level[dep][1]){ level[dep][1] = myNum[arr[now][1]]; } answer(dep + 1, arr[now][1]); } } int main(){ int N, root = -1; cin>>N; for(int i = 1; i<=N; i++){ level[i][0] = N+1; level[i][1] = -1; ex[i][0] = 0; ex[i][1] = 0; int a; cin>> a; cin>> arr[a][0] >> arr[a][1]; arr[arr[a][0]][0] = -1; arr[arr[a][0]][1] = -1; arr[arr[a][1]][0] = -1; arr[arr[a][1]][1] = -1; if(arr[a][0] == root || arr[a][1] == root || root == -1){ root = a; } } ex[root][0] = checkNum(arr[root][0]); ex[root][1] = checkNum(arr[root][1]); myNum[root] = ex[root][0] + 1; fill(root); level[1][0] = myNum[root]; level[1][1] = myNum[root]; answer(2, root); int max = 0, bigLevel = 0; for(int i = 1; i<maxDep; i++){ int tmp = level[i][1] - level[i][0] + 1; if(max < tmp){ bigLevel = i; max = tmp; } } cout<< bigLevel << " " << max; }
3.2. 박인서 ¶
#include <iostream> #define LEN 10001 using namespace std; int tree[LEN][2],maxgap[LEN],mingap[LEN]; int cnt=0,maxdep=0; //왼쪽자식->자기자신->오른쪽 자식 순으로 cnt를 세가며 위치를 지정(너비도 같이 생각) void solve(int node, int depth) { //초기화 및 maxdep 설정 if(depth>maxdep) maxdep=depth,mingap[depth]=1001,maxgap[depth]=-1; if(tree[node][0]!=-1) solve(tree[node][0], depth + 1);//왼쪽 자식 호출 cnt++;//node 1개 증가 //maxgap,mingap 설정 if(mingap[depth]>cnt) mingap[depth]=cnt; if(maxgap[depth]<cnt) maxgap[depth]=cnt; if(tree[node][1]!=-1) solve(tree[node][1], depth + 1);//오른쪽 자식 호출 } int main() { int a, i, num, res=-1, index=0; //입력 cin>>num; for(i=1; i<=num; i++) { cin>>a; cin>>tree[a][0]>>tree[a][1]; } //함수 번호 매기기 solve(1, 1); //너비가 가장 큰 것 찾기 for(i=1; i<=maxdep; i++) if(res<maxgap[i]-mingap[i]) res=maxgap[i]-mingap[i],index=i; //출력 cout<<index<<" "<<res+1<<'\n'; return 0; }
4.1. 15이원준 ¶
0. 루트를 찾으면 모든 입력을 저장한다.(arr에 저장)
1. 각각의 노드들의 왼쪽에 연결된 노드들의 수와 오른쪽에 연결된 노드들의 수를 구한다.(ex에 저장)
2. root노드의 열 넘버는 자신의 왼쪽에 연결된 노드들의 수 + 1 이다.(myNum에 저장)
3. 각 노드의 왼쪽노드의 열 넘버 = (자신의 열넘버) - (왼쪽노드의 오른쪽에 연결된 노드들의 수) - 1 이다. (myNum에 저장)
4. 각 노드의 오른쪽노드의 열 넘버 = (자신의 열넘버) + (오른쪽노드의 왼쪽에 연결된 노드들의 수) + 1 이다.(myNum에 저장)
5. 행에서 가장 왼쪽에 있는 노드의 열넘버와 가장 오른쪽에 있는 노드의 열넘버를 저장한다.(level에 저장)
6. 각 행의 너비를 구하고 가장 큰 값을 찾아 그 행의 번호와 너비를 출력한다.
1. 각각의 노드들의 왼쪽에 연결된 노드들의 수와 오른쪽에 연결된 노드들의 수를 구한다.(ex에 저장)
2. root노드의 열 넘버는 자신의 왼쪽에 연결된 노드들의 수 + 1 이다.(myNum에 저장)
3. 각 노드의 왼쪽노드의 열 넘버 = (자신의 열넘버) - (왼쪽노드의 오른쪽에 연결된 노드들의 수) - 1 이다. (myNum에 저장)
4. 각 노드의 오른쪽노드의 열 넘버 = (자신의 열넘버) + (오른쪽노드의 왼쪽에 연결된 노드들의 수) + 1 이다.(myNum에 저장)
5. 행에서 가장 왼쪽에 있는 노드의 열넘버와 가장 오른쪽에 있는 노드의 열넘버를 저장한다.(level에 저장)
6. 각 행의 너비를 구하고 가장 큰 값을 찾아 그 행의 번호와 너비를 출력한다.