n-ary 트리를 나타내는 'tree'라는 값의 2D 목록과 'color'라는 값의 또 다른 목록이 있다고 가정합니다. 트리는 인접 목록으로 표시되며 루트는 트리[0]입니다.
i번째 노드의 특성 -
-
tree[i]는 자식과 부모입니다.
-
color[i]는 해당 색상입니다.
루트가 N에 있는 하위 트리의 모든 노드가 고유한 색상을 갖는 경우 노드 N을 "특수"라고 부릅니다. 이 트리가 있으므로 특수 노드의 수를 찾아야 합니다.
So, if the input is like tree = [ [1,2], [0], [0,3], [2] ]
색상 =[1, 2, 1, 1]이면 출력은 2가 됩니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
-
결과 :=0
-
dfs(0, -1)
-
반환 결과
-
check_intersection() 함수를 정의합니다. 이것은 색상을 취할 것입니다, child_colors
-
(colors)의 길이 <(child_colors)의 길이인 경우
-
색상의 각 c에 대해 수행
-
child_colors의 c가 0이 아니면
-
참을 반환
-
-
-
-
그렇지 않으면
-
child_colors의 각 c에 대해 수행
-
c가 child_colors에 있으면
-
참을 반환
-
-
-
-
-
dfs() 함수를 정의합니다. 이것은 노드가 필요합니다. 이전
-
색상 :={색상[노드]}
-
트리[노드]의 각 자식에 대해 수행
-
자식이 이전과 같지 않으면
-
child_colors :=dfs(자식, 노드)
-
colors 및 child_colors가 비어 있지 않으면
-
check_intersection(colors, child_colors)이 0이 아니면
-
색상 :=null
-
-
그렇지 않으면
-
if length of (colors)
-
child_colors :=child_colors 또는 색상
-
색상 :=child_colors
-
-
그렇지 않으면
-
색상 :=색상 또는 자식 색상
-
-
-
-
그렇지 않으면
-
색상 :=null
-
-
-
색상이 비어 있지 않으면
-
결과 :=결과 + 1
-
-
색상 반환
-
-
예시
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
import collections
class Solution:
def solve(self, tree, color):
self.result = 0
def dfs(node, prev):
colors = {color[node]}
for child in tree[node]:
if child != prev:
child_colors = dfs(child, node)
if colors and child_colors:
if self.check_intersection(colors, child_colors):
colors = None
else:
if len(colors) < len(child_colors):
child_colors |= colors
colors = child_colors
else:
colors |= child_colors
else:
colors = None
if colors:
self.result += 1
return colors
dfs(0, -1)
return self.result
def check_intersection(self, colors, child_colors):
if len(colors) < len(child_colors):
for c in colors:
if c in child_colors:
return True
else:
for c in child_colors:
if c in colors:
return True
ob = Solution()
print(ob.solve( [
[1,2],
[0],
[0,3],
[2]
], [1, 2, 1, 1])) 입력
[ [1,2], [0], [0,3], [2] ], [1, 2, 1, 1]
출력
2