문제 이해하기
총 n개의 과목을 수강할 수 있으며, 각 과목에는 0부터 n-1까지 번호가 붙어 있다고 가정해 봅시다.
일부 과목은 직접적인 선수과목을 가질 수 있습니다. 예를 들어 과목 0을 수강하려면 먼저 과목 1을 수강해야 한다는 조건은 [1,0] 쌍으로 표현됩니다.
즉, 과목의 개수 n, 직접적인 선수과목 쌍의 목록(prerequisites), 그리고 질의(query) 쌍의 목록(queries)이 주어졌을 때,
각 queries[i]에 대해 과목 queries[i][0]이 과목 queries[i][1]의 선수과목인지 여부를 판단해야 합니다. 최종적으로는 각 질의에 대한 답을 불리언(boolean) 리스트 형태로 반환하면 됩니다.
여기서 중요한 점은 선수과목 관계의 전이성(transitivity)입니다. 과목 a가 과목 b의 선수과목이고, 과목 b가 과목 c의 선수과목이라면, 과목 a 역시 과목 c의 선수과목이 됩니다.
예를 들어 입력이 n = 3, prerequisites = [[1,2],[1,0],[2,0]], queries = [[1,0],[1,2]]라면 출력은 [true, true]가 됩니다.
해결 접근 방법
이 문제는 위상 정렬(Topological Sort)을 활용해 해결할 수 있습니다. 핵심 아이디어는 각 과목마다 '자신의 모든 선수과목 집합'을 유지하면서, 진입 차수(in-degree)가 0인 과목부터 순서대로 처리하는 것입니다. 구체적인 단계는 다음과 같습니다.
- N := 110 상수 정의
- 결과를 저장할 배열 ret 정의
- 진입 차수를 저장할 맵 in 정의
- v의 각 원소 it에 대해 다음을 수행:
- graph[it[0]]의 끝에 it[1] 삽입
- in[it[1]] 값을 1 증가
- 큐 q 정의
- i := 0으로 초기화하고, i < n인 동안 i를 1씩 증가시키며 반복:
- in[i]가 0이면 q에 i 삽입
- 각 과목의 선수과목 집합을 저장할 맵 c 정의
- lvl := 1로 초기화하고, q가 비어 있지 않은 동안 lvl을 1씩 증가시키며 반복:
- sz := q의 크기
- sz가 0이 아니면 매 반복마다 sz를 감소시키면서 수행:
- node := q의 첫 번째 원소
- q에서 해당 원소 제거
- graph[node]의 각 원소 it에 대해:
- in[it] 값 1 감소
- c[node]의 각 원소 x에 대해 c[it]에 x 삽입
- c[it]에 node 삽입
- in[it]가 0이면 it를 q에 삽입
- x(queries)의 각 원소 it에 대해:
- ret의 끝에 c[it[1]] 안에 it[0]이 존재하는지의 여부(빈도)를 삽입
- ret 반환
예제 구현
아래 구현 코드를 통해 더 잘 이해해 봅시다.
#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<bool> v){
cout << "[";
for(int i = 0; i<v.size(); i++){
cout << v[i] << ", ";
}
cout << "]"<<endl;
}
const int N = 110;
class Solution {
public:
vector <int> graph[N];
map <int, set <int>> c;
vector<bool> checkIfPrerequisite(int n, vector<vector<int>>& v, vector<vector<int>>& x) {
vector<bool> ret;
map<int, int> in;
for (auto& it : v) {
graph[it[0]].push_back(it[1]);
in[it[1]]++;
}
queue<int> q;
for (int i = 0; i < n; i++) {
if (in[i] == 0)
q.push(i);
}
map<int, int> idx;
for (int lvl = 1; !q.empty(); lvl++) {
int sz = q.size();
while (sz--) {
int node = q.front();
q.pop();
for (auto& it : graph[node]) {
in[it]--;
for (auto& x : c[node])
c[it].insert(x);
c[it].insert(node);
if (in[it] == 0) {
q.push(it);
}
}
}
}
for (auto& it : x) {
ret.push_back(c[it[1]].count(it[0]));
}
return ret;
}
};
main(){
Solution ob;
vector<vector<int>> prerequisites = {{1,2},{1,0},{2,0}}, queries = {{1,0},{1,2}};
print_vector(ob.checkIfPrerequisite(3, prerequisites, queries));
}동작 원리 요약
그래프를 인접 리스트로 구성한 뒤, 진입 차수가 0인 과목들을 큐에 넣고 BFS 방식으로 처리합니다. 어떤 과목이 처리될 때마다 그 과목이 가진 선수과목 집합(c[node])을 후속 과목들의 집합에 병합하고, 자기 자신도 추가합니다. 이렇게 하면 각 과목에 대해 간접적인 선수과목까지 모두 포함된 집합이 완성되므로, 이후 각 질의에 대해 O(1)에 가깝게 존재 여부만 확인하면 됩니다.
입력
3, {{1,2},{1,0},{2,0}}, {{1,0},{1,2}}출력
[1, 1]