문제 이해
n개의 프로세스가 있다고 가정해 봅시다. 각 프로세스는 PID(프로세스 ID)라는 고유한 식별자를 가지며, PPID(부모 프로세스 ID) 또한 존재합니다.
각 프로세스는 오직 하나의 부모 프로세스만 가지지만, 하나 이상의 자식 프로세스를 가질 수 있습니다. 즉, 전체 구조는 트리(tree) 형태와 같습니다. PPID가 0인 프로세스는 단 하나뿐이며, 이는 부모가 없는 최상위(root) 프로세스를 의미합니다. 모든 PID는 고유한 양의 정수입니다.
프로세스 목록은 두 개의 정수 리스트로 표현됩니다. 첫 번째 리스트에는 각 프로세스의 PID가, 두 번째 리스트에는 그에 대응하는 PPID가 담겨 있습니다. 종료하려는 프로세스의 PID가 주어졌을 때, 최종적으로 종료되는 모든 프로세스의 PID 목록을 구해야 합니다. 이때 어떤 프로세스가 종료되면 그 자식 프로세스들도 모두 함께 종료된다고 가정합니다.
예를 들어 입력이 pid = [1, 3, 10, 5], ppid = [3, 0, 5, 3], kill = 5라면 출력은 [5, 10]이 됩니다.
프로세스 5를 종료하면 그 자식인 프로세스 10도 함께 종료되기 때문입니다.
접근 방법
이 문제는 BFS(너비 우선 탐색)를 활용하면 효율적으로 해결할 수 있습니다. 전체 알고리즘은 다음과 같습니다.
부모 PID를 키로, 해당 자식들의 PID 목록을 값으로 갖는 맵(map) child를 정의합니다.
n := pid의 크기로 설정합니다.
결과를 저장할 배열 ret을 정의합니다.
i := 0부터 i < n까지 반복하면서 다음을 수행합니다.
u := ppid[i]
v := pid[i]
v를 child[u]의 끝에 추가하여 부모-자식 관계를 구성합니다.
큐 q를 정의하고 kill 값을 삽입합니다.
q가 빌 때까지 다음을 반복합니다.
curr := q의 첫 번째 원소
q에서 해당 원소를 제거합니다.
curr을 ret의 끝에 추가합니다.
i := 0부터 child[curr]의 크기까지 반복하며 child[curr][i]를 q에 삽입합니다.
최종 결과 ret을 반환합니다.
예제 코드
아래 구현을 통해 더 잘 이해할 수 있습니다.
#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<auto> v){
cout << "[";
for(int i = 0; i<v.size(); i++){
cout << v[i] << ", ";
}
cout << "]"<<endl;
}
class Solution {
public:
vector<int> killProcess(vector<int>& pid, vector<int>& ppid, int kill) {
map<int, vector<int> > child;
int n = pid.size();
vector<int> ret;
for (int i = 0; i < n; i++) {
int u = ppid[i];
int v = pid[i];
child[u].push_back(v);
}
queue<int> q;
q.push(kill);
while (!q.empty()) {
int curr = q.front();
q.pop();
ret.push_back(curr);
for (int i = 0; i < child[curr].size(); i++) {
q.push(child[curr][i]);
}
}
return ret;
}
};
main(){
Solution ob;
vector<int> v = {1,3,10,5}, v1 = {3,0,5,3};
print_vector(ob.killProcess(v, v1, 5));
}입력
{1,3,10,5},{3,0,5,3},5출력
[5, 10]
복잡도 분석
모든 프로세스를 한 번씩 순회하므로 시간 복잡도는 O(n)입니다. 부모-자식 관계를 저장하는 맵과 큐, 결과 배열에 프로세스 수에 비례하는 공간이 사용되므로 공간 복잡도 역시 O(n)입니다.