두 명의 플레이어가 이진 트리에서 턴제 게임을 한다고 가정합니다. 이 이진 트리의 루트와 트리의 노드 수 n이 있습니다. 여기서 n은 홀수이고 각 노드는 1에서 n까지의 고유한 값을 갖습니다. 처음에 첫 번째 플레이어는 1 <=x <=n으로 값 x에 이름을 지정하고 두 번째 플레이어는 1 <=y <=n으로 값 y에 이름을 지정하며 y !=x와 같은 조건을 유지합니다. 첫 번째 플레이어는 값 x가 있는 노드를 빨간색으로 색칠하고 두 번째 플레이어는 값 y를 가진 노드를 파란색으로 색칠합니다. 그 후, 플레이어는 첫 번째 플레이어부터 차례대로 진행합니다. 각 턴에서 플레이어는 자신의 색상 노드(플레이어 1의 경우 빨간색, 플레이어 2의 경우 파란색)를 선택하고 선택한 노드의 색칠되지 않은 이웃(왼쪽 또는 오른쪽 자식 또는 선택한 노드의 부모)에 색상을 지정합니다. 플레이어가 이러한 방식으로 노드를 사용할 수 없는 경우에만 자신의 차례를 통과해야 합니다. 두 플레이어 모두 자신의 차례를 통과하면 게임이 종료되며 더 많은 노드를 색칠한 플레이어가 승자가 됩니다.
우리가 두 번째 플레이어라고 가정합니다. 게임에서 이기도록 이러한 y를 선택할 수 있으면 true를 반환합니다. 불가능하면 false를 반환합니다.
트리가 다음과 같다면 -
n이 11이고 x가 3이면 두 번째 플레이어가 값이 2인 노드를 사용할 수 있으므로 출력은 참이 됩니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
-
solve()라는 메서드를 정의하면 노드 x, l 및 r이 사용되며 l 및 r은 초기에 false이며 아래와 같이 작동합니다. -
-
노드가 없으면 리턴하고 종료합니다.
-
l이 참이면 leftVal을 1만큼 증가시키고, 그렇지 않으면 r이 참이면 rightVal을 1만큼 증가시킵니다.
-
노드 값이 x이면 solve(노드의 왼쪽, x, true, false)를 호출하고 solve(노드의 오른쪽, x, false, true)를 호출합니다.
-
그렇지 않으면 solve(노드의 왼쪽, x, l, r)를 호출하고 solve(노드의 오른쪽, x, l, r)를 호출합니다.
-
주요 방법은 다음과 같습니다 -
-
nodeToX :=0, leftVal :=0, rightVal :=0
-
해결 호출(루트, x, 거짓, 거짓)
-
nodeToX :=n – leftVal – rightVal – 1
-
temp :=rightVal, nodeToX 및 leftVal의 최대값
-
(nodeToX + leftVal + rightVal – (2*temp)>=0)이면 false를 반환하고, 그렇지 않으면 true
를 반환합니다.
예시(파이썬)
더 나은 이해를 위해 다음 구현을 살펴보겠습니다. −
class TreeNode: def __init__(self, data, left = None, right = None): self.data = data self.left = left self.right = right def insert(temp,data): que = [] que.append(temp) while (len(que)): temp = que[0] que.pop(0) if (not temp.left): if data is not None: temp.left = TreeNode(data) else: temp.left = TreeNode(0) break else: que.append(temp.left) if (not temp.right): if data is not None: temp.right = TreeNode(data) else: temp.right = TreeNode(0) break else: que.append(temp.right) def make_tree(elements): Tree = TreeNode(elements[0]) for element in elements[1:]: insert(Tree, element) return Tree class Solution(object): def btreeGameWinningMove(self, root, n, x): self.nodeToX = 0 self.leftVal = 0 self.rightVal = 0 self.solve(root,x) self.nodeToX = n - self.leftVal - self.rightVal - 1 temp = max(self.rightVal,max(self.nodeToX,self.leftVal)) return not (self.nodeToX + self.leftVal + self.rightVal - (2*temp)>=0) def solve(self,node,x,l= False,r = False): if not node: return if l: self.leftVal+=1 elif r: self.rightVal+=1 if node.data == x: self.solve(node.left,x,True,False) self.solve(node.right,x,False,True) else: self.solve(node.left,x,l,r) self.solve(node.right,x,l,r) ob = Solution() root = make_tree([1,2,3,4,5,6,7,8,9,10,11]) print(ob.btreeGameWinningMove(root, 11, 3))
입력
[1,2,3,4,5,6,7,8,9,10,11] 11 3
출력
true