여러 세대로 구성된 가족이 있다고 가정해 봅시다. 아버지와 그의 자녀들, 그리고 자녀들의 할머니까지 한데 모인 가족처럼 말입니다. 하지만 어떤 가족에서든 출생과 사망은 반복되기 마련입니다.
가족 안에서 최연장자는 '가장(head)'으로 불립니다. 가장이 사망하면 직계 후계자인 자녀가 새로운 가장 자리를 승계합니다. 우리는 세 가지 함수를 구현해야 합니다. 첫 번째 함수는 가족에게 자녀가 태어났을 때 사용되며, 부모의 이름과 자녀의 이름을 입력받아 기록에 추가하는 역할을 합니다.
두 번째 함수는 가족 구성원이 사망했을 때 사용됩니다. 고인의 이름을 입력받아 기록에서 제거합니다.
세 번째 함수는 상속 순서를 알려줍니다. 호출될 때마다 현재 시점의 상속 순서를 출력합니다.
예를 들어 입력 순서가 출생, 출생, 출생, 출생, 출생, 사망, 상속, 사망, 상속이라면 출력 결과는 ['Zach', 'Jesse', 'Ursula', 'Ryan', 'Thea']와 ['Jesse', 'Ursula', 'Ryan', 'Thea']가 됩니다.
시나리오 살펴보기
처음 가족의 가장은 Paul입니다.
Paul은 Zach과 Jesse라는 두 자녀를 차례로 얻었습니다.
Jesse는 다시 Ursula, Ryan, Thea 세 자녀를 두었는데, Ursula가 맏이이고 Thea가 막내입니다.
이후 Paul이 사망하면 상속 순서는 ['Zach', 'Jesse', 'Ursula', 'Ryan', 'Thea']가 됩니다.
그다음 Zach마저 사망하면 상속 순서는 ['Jesse', 'Ursula', 'Ryan', 'Thea']로 바뀝니다.
문제 해결 접근 방법
이 문제는 깊이 우선 탐색(DFS)을 활용하면 효율적으로 해결할 수 있습니다. 단계별로 살펴보겠습니다.
family : 리스트를 값으로 갖는 딕셔너리(map)를 생성하여 각 구성원의 자녀 목록을 관리합니다.
head : 현재 가족의 가장 이름을 저장합니다.
dead : 사망한 구성원을 추적하는 집합(set)입니다.
birth() 함수를 정의합니다. 매개변수는 p_name, c_name입니다.
family[p_name] 리스트의 끝에 c_name을 추가합니다. 이렇게 하면 자녀가 태어난 순서가 자동으로 유지됩니다.
death() 함수를 정의합니다. 매개변수는 name입니다.
name을 dead 집합에 추가합니다.
inheritance() 함수를 정의합니다.
ans : 결과를 담을 새로운 리스트를 만듭니다.
depth_search(head)를 호출합니다.
ans를 반환합니다.
depth_search() 함수를 정의합니다. 매개변수는 current입니다.
current가 dead 집합에 없다면 ans의 끝에 current를 추가합니다.
family[current]에 있는 각 자녀에 대해 depth_search(child)를 재귀 호출합니다.
전위(preorder) 방식으로 가계도 트리를 순회하기 때문에 항상 부모가 자식보다 먼저 방문되고, 같은 부모의 자녀들은 태어난 순서대로 처리됩니다. 덕분에 사망 여부만 확인하면 정확한 상속 순서를 손쉽게 얻을 수 있습니다.
구현 예제
다음 파이썬 구현을 통해 더 잘 이해해 봅시다.
from collections import defaultdict
class Solution:
def __init__(self, head_name):
self.family = defaultdict(list)
self.head = head_name
self.dead = set()
def birth(self, p_name, c_name):
self.family[p_name].append(c_name)
def death(self, name):
self.dead.add(name)
def inheritance(self):
self.ans = []
self.depth_search(self.head)
return self.ans
def depth_search(self, current):
if current not in self.dead:
self.ans.append(current)
for child in self.family[current]:
self.depth_search(child)
ob = Solution('Paul')
ob.birth('Paul', 'Zach')
ob.birth('Paul', 'Jesse')
ob.birth('Jesse', 'Ursula')
ob.birth('Jesse', 'Ryan')
ob.birth('Jesse', 'Thea')
ob.death('Paul')
print(ob.inheritance())
ob.death('Zach')
print(ob.inheritance())
입력
ob = Solution('Paul')
ob.birth('Paul', 'Zach')
ob.birth('Paul', 'Jesse')
ob.birth('Jesse', 'Ursula')
ob.birth('Jesse', 'Ryan')
ob.birth('Jesse', 'Thea')
ob.death('Paul')
print(ob.inheritance())
ob.death('Zach')
print(ob.inheritance())
출력
['Zach', 'Jesse', 'Ursula', 'Ryan', 'Thea'] ['Jesse', 'Ursula', 'Ryan', 'Thea']