U E D R , A S I H C RSS

1R/2015_09_12

Difference between r1.4 and the current

@@ -4,7 +4,7 @@
* [https://www.acmicpc.net/problem/2250|트리의 높이와 너비]

= 참가자 =
* 15이원준
* 15이원준, 박인서
= 코드 =
== 15이원준 ==
{{{
@@ -98,16 +98,73 @@
}
}}}
== 박인서 ==
{{{
#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이원준 ==
1. 각각의 노드들의 왼쪽에 연결된 노드들의 수와 오른쪽에 연결된 노드들의 수를 구한다.
2. root노드의 열 넘버는 자신의 왼쪽에 연결된 노드들의 수 + 1 이다.
3. 각 노드의 왼쪽노드의 열 넘버 = (자신의 열넘버) - (왼쪽노드의 오른쪽에 연결된 노드들의 수) - 1 이다.
4. 각 노드의 오른쪽노드의 열 넘버 = (자신의 열넘버) + (오른쪽노드의 왼쪽에 연결된 노드들의 수) + 1 이다.
5. 행에서 가장 왼쪽에 있는 노드의 열넘버와 가장 오른쪽에 있는 노드의 열넘버를 저장한다.
0. 루트를 찾으면 모든 입력을 저장한다.(arr에 저장)
1. 각각의 노드들의 왼쪽에 연결된 노드들의 수와 오른쪽에 연결된 노드들의 수를 구한다.(ex에 저장)
2. root노드의 열 넘버는 자신의 왼쪽에 연결된 노드들의 수 + 1 이다.(myNum에 저장)
3. 각 노드의 왼쪽노드의 열 넘버 = (자신의 열넘버) - (왼쪽노드의 오른쪽에 연결된 노드들의 수) - 1 이다. (myNum에 저장)
4. 각 노드의 오른쪽노드의 열 넘버 = (자신의 열넘버) + (오른쪽노드의 왼쪽에 연결된 노드들의 수) + 1 이다.(myNum에 저장)
5. 행에서 가장 왼쪽에 있는 노드의 열넘버와 가장 오른쪽에 있는 노드의 열넘버를 저장한다.(level에 저장)
6. 각 행의 너비를 구하고 가장 큰 값을 찾아 그 행의 번호와 너비를 출력한다.
== 박인서 ==
{{{
1. 이 문제를 어떻게 해야 할 것인가?
일단 노드의 갯수가 1000개 이하이므로 일일히 노드에 대하여 탐색을 하여도 시간이 부족하지는 않다. 따라서 일일이 탐색을 하는 것을 목적으로 한다.
 
2. 중위순회란 무엇인가?
위키 페이지를 참고하여주세요.
https://ko.wikipedia.org/wiki/%ED%8A%B8%EB%A6%AC_%EC%88%9C%ED%9A%8C
 
3. 그러면 이 문제는 어떻게 해결해야 되는가?
이 문제에서 열 번호가 왼쪽자식->자기자신->오른쪽자식(중위순회) 순서로 되어 있다. 따라서, 이를 따라서 함수를 호출하여 번호를 매긴다. 그리고 depth에 따라서 배열에 열 번호의 최소값과 최대값을 저장하여 해결 할 수 있다.
}}}
== 곽정흠 ==




1. 오늘의 문제

2. 참가자

  • 15이원준, 박인서

3. 코드

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 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;
}

3.3. 곽정흠


4. 아이디어

4.1. 15이원준

0. 루트를 찾으면 모든 입력을 저장한다.(arr에 저장)
1. 각각의 노드들의 왼쪽에 연결된 노드들의 수와 오른쪽에 연결된 노드들의 수를 구한다.(ex에 저장)
2. root노드의 열 넘버는 자신의 왼쪽에 연결된 노드들의 수 + 1 이다.(myNum에 저장)
3. 각 노드의 왼쪽노드의 열 넘버 = (자신의 열넘버) - (왼쪽노드의 오른쪽에 연결된 노드들의 수) - 1 이다. (myNum에 저장)
4. 각 노드의 오른쪽노드의 열 넘버 = (자신의 열넘버) + (오른쪽노드의 왼쪽에 연결된 노드들의 수) + 1 이다.(myNum에 저장)
5. 행에서 가장 왼쪽에 있는 노드의 열넘버와 가장 오른쪽에 있는 노드의 열넘버를 저장한다.(level에 저장)
6. 각 행의 너비를 구하고 가장 큰 값을 찾아 그 행의 번호와 너비를 출력한다.

4.2. 박인서

1. 이 문제를 어떻게 해야 할 것인가?
일단 노드의 갯수가 1000개 이하이므로 일일히 노드에 대하여 탐색을 하여도 시간이 부족하지는 않다. 따라서 일일이 탐색을 하는 것을 목적으로 한다.

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

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

4.3. 곽정흠

Valid XHTML 1.0! Valid CSS! powered by MoniWiki
last modified 2016-09-13 02:30:30
Processing time 22.2790 sec