1068번 - 트리
1. 주어진 트리는 이진 트리인가?
자식 노드의 갯수가 2를 초과할 수 있는지?
====
8
-1 0 0 0 0 2 2 2
1
2. N개의 노드가 하나의 루트 노드를 공유하는가?
문제에서 "하나의 트리를 구성하는 N개의 노드" 라는 문장이 있으면 명확할듯 합니다.
코딩하다가 괜히 헛고생할거 같아서 풀어보신 분들의 의견을 구해봅니다.
(일단 이 문제는 패쓰! ㅎㅎ)
모두 대답할 필요가 없는 질문들이네요. 문제는 충분히 엄밀합니다.
1. 추가적인 조건이 없으므로 일반적인 트리입니다.
2. 둘 이상의 트리를 구성하면 그건 트리가 아니라 숲입니다.
입력으로 주어진 트리에서 입력으로 주어진 노드를 지웠을 때, 리프 노드의 개수를 출력한다.
조건이 다 주어졌네요.
트리의 정의는 위키 참고하세요.
https://en.wikipedia.org/wiki/Tree_(graph_theory)
문제가 충분히 엄밀한가요?
트리의 정의와는 별개로
한 노드를 제거하면 여러개의 트리가 남게되고 각각의 트리의 root 가 어디인지는 문제에 나와있지 않으니까 문제 설명이 불충분한 건 맞는것 같은데요.
"0번 노드부터 N-1번 노드까지, 각 노드의 부모가 주어진다. 만약 부모가 없다면 (루트) -1이 주어진다."
한 노드를 제거하면 여러개의 트리가 '남게'되고 각각의 트리의 root 가 어디인지는 문제에 나와있지 않으니까 문제 설명이 불충분한 건 맞는것 같은데요.
말을 풀어서 쓰면 노드의 수가 5 이상인 사향 트리가 있을 때, 루트와 리프가 아닌 하나의 노드가 제거될 노드로 주어진다고하면, 제거 된 후에는 두 개의 트리로 쪼개어 지는데 각각 의 쪼개어진 트리의 루트를 무엇으로 볼 것이냐에 따라서 리프 노드의 개수는 달라지지요.
예시에 색칠되어 있듯이, 노드를 제거하면 그 노드의 자손도 제외됩니다. 그러므로 하나의 트리만 남고, 그 트리의 루트는 변하지 않습니다.
문제 설명에 '트리가 주어졌을 때'라고 나와 있습니다.
또한 리프 노드를 제거하는 경우, 입력에서 주어진 모든 노드들이 제거됩니다. 따라서 리프 노드의 갯수는 0이 될 것입니다.
댓글을 작성하려면 로그인해야 합니다.
yeoriseo 7년 전
1. 주어진 트리는 이진 트리인가?
자식 노드의 갯수가 2를 초과할 수 있는지?
====
8
-1 0 0 0 0 2 2 2
1
====
2. N개의 노드가 하나의 루트 노드를 공유하는가?
문제에서 "하나의 트리를 구성하는 N개의 노드" 라는 문장이 있으면 명확할듯 합니다.
코딩하다가 괜히 헛고생할거 같아서 풀어보신 분들의 의견을 구해봅니다.
(일단 이 문제는 패쓰! ㅎㅎ)