글 읽기 - 1068(트리)문제 질문입니다. 왜 틀린건지 모르겠습니다.

boffin 6년 전 0

어느 부분에서 반례가 있는지 모르겠습니다ㅠ 도와주세요!

#include<stdio.h>

typedef struct nodeinfo {
	int par;//해당 노드의 부모입니다.
	int leafcnt;//해당 노드가 가지는 1촌자식의 수입니다.
}nodeinfo;


int main() {
	int N,del;
	int check=0;
	int que[51] = { 0 };
	int cnt = 0;
	int front = 0, tail = 0;
	nodeinfo node[51] = { 0 };
	int ppar;
	
	scanf("%d", &N);//노드의 개수를 받습니다.
	for (int i = 0; i < N; i++) { 
		scanf("%d", &node[i].par); 
		if (node[i].par == -1)ppar = i;//최상위 부모 노드를 찾습니다.
	}
	scanf("%d", &del);//삭제할 노드를 받습니다.

	for (int i = 1; i < N; i++) {//각 자신의 1촌 자식의 수를 셉니다.
		if (check == node[i].par) {
			node[check].leafcnt++;
		}

		if (check != node[i + 1].par) {
			check = node[i + 1].par;
		}
	}


	if (del != ppar) {//삭제할 노드가 최상위 부모가 아닌 경우입니다.
		node[node[del].par].leafcnt--;//노드를 삭제하고 삭제된 노드의 부모노드가 가지는 자식수를 1개줄입니다.
		node[del].par = -2;//삭제한 노드를 표시해줍니다
		que[tail] = 0;//0은 삭제 되지 않았으니 우선 큐에 0을놓고 비교를 할 것 입니다.
		
		while (front <= tail) {
			for (int i = 1; i < N; i++) {
				if (que[front] == node[i].par) {//현재 큐의 위치에 해당하는 값고 각 노드들의 부모노드를 비교합니다.
					que[++tail] = i;//그리고 부모노드가 큐에 존재하면 현재 노드도 큐에 넣습니다.
				}
			}
			front++;//front를 증가시켜 계속 반복 합니다.
		}

		//현재 큐에 들어가 있는 노드들은 잔존한 노드들만 들어가 있게 됩니다.
		for (int i = 0; i < N; i++) {
			if (node[que[i]].leafcnt == 0)cnt++;
		}//잔존한 노드들중 자식의 갯수가 0인 녀석들을 찾아 수를 셉니다.
	}
	else cnt = 0;//삭제할 노드가 최상위 부모면 전체 노드 수는 0개가 됩니다.


	printf("%d", cnt);
	//for (int i = 0; i < N; i++)printf("%d 의 자식수: %d\n", i,node[i].leafcnt);
}

djm03178 6년 전 1

-1 0

정답은 1인데, 2를 출력합니다.

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

문제

문제

출처

ICPC

1068(트리)문제 질문입니다. 왜 틀린건지 모르겠습니다.

boffin 6년 전 0

djm03178 6년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말