글 읽기 - 요거 어디가 틀렸을까요~!

cardbt 7년 전 0

안녕하세요.

게시판의 반례들을 다 돌려보고, 몇 가지 생각나는데로 돌려봤는데, 다 맞게 나왔습니다.

반례가 될만한게 어떤것이 있을까요?

기본 컨셉은 dfs로 돌면서 각 노드별로 자식 노드가 몇개인지를 가지고 있습니다.

최종 값음 루트노드의 자식 값에서 제거하는 노드의 자식값을 빼서 결과를 도출하는 방식인데요.

어디가 잘못된건지 모르겠어요 ㅠㅠ

의견 부탁드립니다~!

N, leaf_cnt[50], node[50];
int dfs(int idx)
{
	int i, exist = 0;
	for (i=0;i<N;i++)
	{
		if (i==idx) continue;
		if (node[i]==idx)
		{
			exist++;
			leaf_cnt[idx] += dfs(i);
		}
	}
	if (exist==0) 
	{
		leaf_cnt[idx]++;
	}
	
	return leaf_cnt[idx];
}

main()
{
	int i, e, start = 0;
	scanf("%d", &N);

	for (i=0;i<N;i++)
	{
		scanf("%d", &node[i]);
		if (node[i] == -1) start = i;
	}

	scanf("%d", &e);

	dfs(start);

	if (start == e) printf("0"); // 루트를 날리면 0
	else if (leaf_cnt[start]-leaf_cnt[e] == 0) printf("1"); // 루트 빼고 다 날아가면 루트가 자식이니 1
	else printf("%d", leaf_cnt[start]-leaf_cnt[e]);
}

gallopsys 7년 전 2

3 6 6 -1 0 6 3

위의 데이터를 입력하면 4가 나와야하는데, 해당 코드는 3을 출력하고 있습니다.

cardbt 7년 전 0

아.. leaf node가 제거 됐을때가 고려가 안되어 있네요.... 킁

감사합니다 ㅠㅠ

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

문제

문제

출처

ICPC

요거 어디가 틀렸을까요~!

cardbt 7년 전 0

gallopsys 7년 전 2

cardbt 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말