Gegeven is een groep personen die elkaar al dan niet kennen. Indien een persoon door iedereen uit de groep gekend is maar zelf niemand kent, zeggen we dat deze persoon beroemd is. Ontwerp en implementeer een efficiënt algoritme om een beroemdheid op te sporen door zo weinig mogelijk vragen te stellen van de vorm “kent persoon A persoon B?”

Opgave

Schrijf een Python-functie zoekBeroemdheid(groep: list), die de beroemdheid van een gegeven groep teruggeeft; als de groep geen beroemdheid heeft, moet None teruggegeven worden.

De groep wordt voorgesteld als een matrix. Er wordt gezegd dat persoon 0 persoon 1 kent indien groep[0][1] == True en dat persoon 0 persoon 1 niet kent als groep[0][1] == False. Een persoon is beroemd wanneer zijn volledige rij uit True bestaat en zijn volledige kolom uit False bestaat, behalve bij de vakjes op de diagonaal deze worden op None gezet.

De correctheid van je code wordt automatisch getest, de efficiëntie denk je zelf over na.

Voorbeelden

>>> zoekBeroemdheid([[None, False], [True, None]])
0
>>> zoekBeroemdheid([[None, False, False], [True, None, True], [True, False, None]])
0
>>> zoekBeroemdheid([[None, True, False], [False, None, False], [True, True, None]])
1
>>> zoekBeroemdheid([[None, False, True], [False, None, True], [False, False, None]])
2
>>> zoekBeroemdheid([[None, False, False ], [False, None, False], [False, False, None]])