[LeetCode] 582. Kill Process

 Computer Science를 공부한 사람이라면 익숙한 pid(process id)와 ppid(parent process id)의 개념이 담긴 문제다. 해당 문제에서 각 process는 1개의 parent process만을 가질 수 있고 반면에 parent process는 여러 child process를 가질 수 있다. 해당 문제의 예시 그림으론 Tree 형태로 제시가 됐고, kill을 하기 위한 pid가 input으로 주어지고, 해당 process를 비롯해 연쇄적으로 모든 child process를 kill을 하기 위해 필요한 모든 pid를 List의 형태로 반환하는 문제다.

 

Input: pid = [1,3,10,5], ppid = [3,0,5,3], kill = 5
Output: [5,10]
Explanation: The processes colored in red are the processes that should be killed.

 

 defaultdict을 활용해 구현했고, key로는 pid가 value로는 해당 pid의 모든 child pid를 List의 형태로 담았다. 이에 따라 input인 kill을 바탕으로 defaultdict의 value를 확인해 나가며 ret에 pid를 append해 반환하는 logic이다.

 

class Solution:
    def killProcess(self, pid: List[int], ppid: List[int], kill: int) -> List[int]:
        n = len(pid)
        d = defaultdict(list)
        q = deque()
        ret = []

        for i in range(n):
            d[ppid[i]].append(pid[i])

        q.append(kill)
        ret.append(kill)
        
        while q:
            c = q.popleft()
            cl = d[c]
            
            for i, item in enumerate(cl):
                q.append(item)
                ret.append(item)

        return ret