글 읽기 - 실수할 만한 것을 다 고려해봤는데 틀렸습니다.

james66won 4년 전 0

1. 첫번째 입력값이 반드시 루트노드란 보장이 없다.

2. 순서대로 입력이 주어지지 않는다.

위 두가지 조건을 모두 생각하여 풀어보았는데 틀렸다고 나옵니다. 아울러 극단적인 케이스

1
1 -1 -1

또는

3
1 2 -1
2 3 -1
3 -1 -1

모두 출력이 1 1로 잘 나왔습니다.

한번만 봐주시면 정말 감사하겠습니다.

#include <stdio.h>

// left child랑 right child를 저장하는 구조체
typedef struct {
	int left;
	int right;
} Node;

//cnt는 중위순회를 하면서 열 번호를 부여하는 변수, D는 최대 깊이를 저장
//Min은 해당 level에서 가장 작은 열 번호를 저장, Max는 해당 level에서 가장 큰 열 번호를 저장
int N, cnt=1, D=0, ans, Min[15]={0,}, Max[15]={0,};
Node A[10001]; // 최대 노드 10000개 따라서 index가 10000까지 있을 수 있으므로 10001개 할당.

// i는 노드 번호, d는 level, 중위순회 과정
void dfs(int i, int d) {
	if (i==-1) return; // 유효한 노드가 아니므로 return
	if (d>D) D=d; // 더 깊은 level에 도달했다면 D를 갱신
	dfs(A[i].left, d+1);
	if (Min[d]==0||cnt<Min[d]) Min[d]=cnt; // 해당 level의 노드를 처음 방문했거나 더 작은 열 번호를 찾았다면 갱신
	if (Max[d]==0||cnt>Max[d]) Max[d]=cnt; // 해당 level의 노드를 처음 방문했거나 더 큰 열 번호를 찾았다면 갱신
	cnt++; // 열 번호 1 증가
	dfs(A[i].right, d+1);
}

int main(void) {
	int v[10001]={0,}, a, b, c, root; // root는 루트노드 번호, v배열은 루트노드를 찾기 위한 배열(child로 등장했다면 방문체크함)
	scanf("%d", &N);
	for (int i=1; i<=N; i++) {
		scanf("%d %d %d", &a, &b, &c);
		A[a].left=b;
		A[a].right=c;
		if (b!=-1) v[b]=1; // child로 등장했으므로 v배열에 방문체크
		if (c!=-1) v[c]=1; // child로 등장했으므로 v배열에 방문체크
	}
	for (int i=1; i<=N; i++) {
		if (v[i]==0) {
			root=i; // 루트노드는 한번도 child로 등장하지 않았으므로 v[i]가 0
			break;
		}
	}
	dfs(root, 1); // 루트노드를 시작으로 중위순회
	for (int i=1; i<=D; i++) {
		if (i==1||Max[i]-Min[i]>Max[ans]-Min[ans]) ans=i; // 너비가 가장 큰 level을 ans에 저장하는 과정
	}
	printf("%d %d\n", ans, Max[ans]-Min[ans]+1); // level과 그 level에서의 너비 값 출력
	return 0;
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

실수할 만한 것을 다 고려해봤는데 틀렸습니다.

james66won 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말