yeoriseo   4년 전

1. 주어진 트리는 이진 트리인가?

자식 노드의 갯수가 2를 초과할 수 있는지?

====

8

-1 0 0 0 0 2 2 2

1

====


2. N개의 노드가 하나의 루트 노드를 공유하는가?

문제에서 "하나의 트리를 구성하는 N개의 노드" 라는 문장이 있으면 명확할듯 합니다.


코딩하다가 괜히 헛고생할거 같아서 풀어보신 분들의 의견을 구해봅니다.

(일단 이 문제는 패쓰! ㅎㅎ)

koosaga   4년 전

모두 대답할 필요가 없는 질문들이네요. 문제는 충분히 엄밀합니다. 

jh05013   4년 전

1. 추가적인 조건이 없으므로 일반적인 트리입니다.

2. 둘 이상의 트리를 구성하면 그건 트리가 아니라 숲입니다.

chogahui05   4년 전

입력으로 주어진 트리에서 입력으로 주어진 노드를 지웠을 때, 리프 노드의 개수를 출력한다.

조건이 다 주어졌네요.

트리의 정의는 위키 참고하세요.

https://en.wikipedia.org/wiki/Tree_(graph_theory)

lucidash   4년 전

문제가 충분히 엄밀한가요?

트리의 정의와는 별개로

한 노드를 제거하면 여러개의 트리가 남게되고  각각의 트리의 root 가 어디인지는 문제에 나와있지 않으니까   문제 설명이 불충분한 건 맞는것 같은데요. 

jh05013   4년 전

"0번 노드부터 N-1번 노드까지, 각 노드의 부모가 주어진다. 만약 부모가 없다면 (루트) -1이 주어진다."

lucidash   4년 전

한 노드를 제거하면 여러개의 트리가 '남게'되고  각각의 트리의 root 가 어디인지는 문제에 나와있지 않으니까   문제 설명이 불충분한 건 맞는것 같은데요. 


lucidash   4년 전

말을 풀어서 쓰면   노드의 수가 5 이상인  사향 트리가 있을 때,  루트와 리프가 아닌 하나의 노드가 제거될 노드로 주어진다고하면,   제거 된 후에는 두 개의 트리로 쪼개어 지는데 각각 의 쪼개어진 트리의  루트를 무엇으로 볼 것이냐에 따라서  리프 노드의 개수는 달라지지요. 

jh05013   4년 전

예시에 색칠되어 있듯이, 노드를 제거하면 그 노드의 자손도 제외됩니다. 그러므로 하나의 트리만 남고, 그 트리의 루트는 변하지 않습니다.

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