ZeroWiki - User contributions [en]

1R/2015 09 12

2016-09-12T15:50:10Z

223.62.229.104:

__TOC__

= 오늘의 문제 =
* [https://www.acmicpc.net/problem/2250|트리의 높이와 너비]

= 참가자 =
* 15이원준
= 코드 =
== 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;
}
== 박인서 ==
#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 num, root;
//입력
cin >> num;
for (int i = 1; i <= num; i++)
{
int a;
cin >> a;
cin >> tree[a][0] >> tree[a][1];
if (i==1 || tree[a][0] == root || tree[a][1] == root) root = a;
}
//함수 번호 매기기
solve(root, 1);
//너비가 가장 큰 것 찾기
int res = -1, index = 0;
for (int 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;
}

== 곽정흠 ==

= 아이디어 =
== 15이원준 ==
# 루트를 찾으면 모든 입력을 저장한다.(arr에 저장)
# 각각의 노드들의 왼쪽에 연결된 노드들의 수와 오른쪽에 연결된 노드들의 수를 구한다.(ex에 저장)
# root노드의 열 넘버는 자신의 왼쪽에 연결된 노드들의 수 + 1 이다.(myNum에 저장)
# 각 노드의 왼쪽노드의 열 넘버 = (자신의 열넘버) - (왼쪽노드의 오른쪽에 연결된 노드들의 수) - 1 이다. (myNum에 저장)
# 각 노드의 오른쪽노드의 열 넘버 = (자신의 열넘버) + (오른쪽노드의 왼쪽에 연결된 노드들의 수) + 1 이다.(myNum에 저장)
# 행에서 가장 왼쪽에 있는 노드의 열넘버와 가장 오른쪽에 있는 노드의 열넘버를 저장한다.(level에 저장)
# 각 행의 너비를 구하고 가장 큰 값을 찾아 그 행의 번호와 너비를 출력한다.
== 박인서 ==
1. 이 문제를 어떻게 해야 할 것인가?
일단 노드의 갯수가 1000개 이하이므로 일일히 노드에 대하여 탐색을 하여도 시간이 부족하지는 않다. 따라서 일일이 탐색을 하는 것을 목적으로 한다.

2. 중위순회란 무엇인가?
위키 페이지를 참고하여주세요.
https://ko.wikipedia.org/wiki/%ED%8A%B8%EB%A6%AC_%EC%88%9C%ED%9A%8C

3. 그러면 이 문제는 어떻게 해결해야 되는가?
이 문제에서 열 번호가 왼쪽자식->자기자신->오른쪽자식(중위순회) 순서로 되어 있다. 따라서, 이를 따라서 함수를 호출하여 번호를 매긴다. 그리고 depth에 따라서 배열에 열 번호의 최소값과 최대값을 저장하여 해결 할 수 있다.

== 곽정흠 ==

1R/2015 09 12

2016-09-12T15:49:39Z

223.62.229.104:

__TOC__

= 오늘의 문제 =
* [https://www.acmicpc.net/problem/2250|트리의 높이와 너비]

= 참가자 =
* 15이원준
= 코드 =
== 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;
}
== 박인서 ==
#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 num, root;
//입력
cin >> num;
for (int i = 1; i <= num; i++)
{
int a;
cin >> a;
cin >> tree[a][0] >> tree[a][1];
if (i==1 || tree[a][0] == root || tree[a][1] == root) root = a;
}
//함수 번호 매기기
solve(root, 1);
//너비가 가장 큰 것 찾기
int res = -1, index = 0;
for (int 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;
}

== 곽정흠 ==

= 아이디어 =
== 15이원준 ==
# 루트를 찾으면 모든 입력을 저장한다.(arr에 저장)
# 각각의 노드들의 왼쪽에 연결된 노드들의 수와 오른쪽에 연결된 노드들의 수를 구한다.(ex에 저장)
# root노드의 열 넘버는 자신의 왼쪽에 연결된 노드들의 수 + 1 이다.(myNum에 저장)
# 각 노드의 왼쪽노드의 열 넘버 = (자신의 열넘버) - (왼쪽노드의 오른쪽에 연결된 노드들의 수) - 1 이다. (myNum에 저장)
# 각 노드의 오른쪽노드의 열 넘버 = (자신의 열넘버) + (오른쪽노드의 왼쪽에 연결된 노드들의 수) + 1 이다.(myNum에 저장)
# 행에서 가장 왼쪽에 있는 노드의 열넘버와 가장 오른쪽에 있는 노드의 열넘버를 저장한다.(level에 저장)
# 각 행의 너비를 구하고 가장 큰 값을 찾아 그 행의 번호와 너비를 출력한다.
== 박인서 ==
1. 이 문제를 어떻게 해야 할 것인가?

일단 노드의 갯수가 1000개 이하이므로 일일히 노드에 대하여 탐색을 하여도 시간이 부족하지는 않다. 따라서 일일이 탐색을 하는 것을 목적으로 한다.
2. 중위순회란 무엇인가?

위키 페이지를 참고하여주세요.
https://ko.wikipedia.org/wiki/%ED%8A%B8%EB%A6%AC_%EC%88%9C%ED%9A%8C
3. 그러면 이 문제는 어떻게 해결해야 되는가?

이 문제에서 열 번호가 왼쪽자식->자기자신->오른쪽자식(중위순회) 순서로 되어 있다. 따라서, 이를 따라서 함수를 호출하여 번호를 매긴다. 그리고 depth에 따라서 배열에 열 번호의 최소값과 최대값을 저장하여 해결 할 수 있다.

== 곽정흠 ==

1R/2015 09 12

2016-09-12T15:40:07Z

223.62.229.104: