글 읽기 - 왜 틀렸는지 모르겠습니다.

apwgg045 6년 전 0

코드 작동 방식

0. 노드를 50개 저장하는 배열을 입력받고, 루트노드의 주소값을 root에 저장하며, 각 노드에 자식이 생길 때마다 nOfChild값을 1씩 증가시킴

1. 제거하려는 노드의 부모 노드로 접근하여 nOfChild를 1 빼고, 부모 노드 포인터를 NULL로 설정

(루트 노드를 제거한 경우는 if문으로 따로 처리)

2. 노드가 저장되어 있는 배열을 돌면서 nOfChild 값으로 리프 노드를 확인

3. while문을 통해 부모 노드가 없는 노드(루트노드)까지 올라가서, root와 주소값을 비교함으로써 제거된 노드의 리프노드들을 걸러낼 수 있음(2에 의해)

생각할 수 있는 예외도 전부 처리했고 결과도 맞게 나오는데 오답처리가 되는 이유를 모르겠습니다.

#include<stdio.h>

typedef struct node {
  struct node *parent;
  int nOfChildren;
}node;

int main() {
  int n, parentNode, elimNode, nodeCnt = 0;
  node tree[50];
  node *tempNode, *root;
  scanf("%d", &n);
  for(int i = 0; i < n; i++) {
    scanf("%d", &parentNode);
    if(parentNode == -1) { //부모 노드 지정
      tree[i].parent = NULL;
      root = &tree[i];
    }
    else {
      tree[i].parent = &tree[parentNode];
      tree[parentNode].nOfChildren++;
    }
  }

  scanf("%d", &elimNode); //노드 제거
  if(tree[elimNode].parent != NULL) { //널포인터 접근 방지
  tree[elimNode].parent->nOfChildren--; 
  tree[elimNode].parent = NULL;
  }

  for(int i = 0; i < n; i++) {
    if(&tree[elimNode] == root) break; 

    if(tree[i].nOfChildren == 0) { //리프 노드 확인
      tempNode = &tree[i];
      while(tempNode->parent != NULL) { //루트 노드 확인
        tempNode = tempNode->parent;
      }
      if(tempNode == root) {
        nodeCnt++;
      }
    }
  }
  printf("%d\n", nodeCnt);
  return 0;
}