반응형
이 문제는 위상 정렬을 이용하여 풀어야 한다.
위상 정렬이란 자신을 가리키는 노드들이 전부 자신 노드에 방문을 했을 때 다음 노드로 이동할 수 있게 하는 알고리즘이다. 즉, 진입차수가 0인 노드들을 큐에 넣으며 시작하고, 큐에서 꺼낸 노드의 인접노드의 진입 차수를 1씩 감소시키며, 이 결과로 진입 차수가 0이 된 노드들을 다시 큐에 넣는 과정을 반복하는 알고리즘이다.
이전 건물을 다 짓기 전까지는 현재 건물을 짓지 못한다는 조건이 있으므로 위상 정렬을 이용해야 한다는 것이다.
그리고 시간 초과가 나지않게 동적계획법(DP)도 병행하였다. 위상정렬을 수행하며, 이 건물(노드)을 짓는데 걸리는 누적 시간을 업데이트 해주는 것이다. 이전 건물들이 모두 세워져야 현재 건물을 세울 수 있기 때문에 max함수를 이용하여 업데이트 해주었다. 자신을 가리키는 노드가 여러 개일 때 그 갯수만큼 누적시간정보가 들어올텐데 그중 max값을 DP값으로 정했다는 의미다.
#include <iostream>
#include <algorithm>
#include <string.h>
#include <vector>
#include <queue>
#include <stack>
#include <string>
using namespace std;
int indegree[1001];
int createtime[1001];
int d[1001];
vector<int> a[1001];
queue<int> q;
int n, k, m, ans;
int maxi(int a,int b){
if(a>b) return a;
else return b;
}
int mini(int a,int b){
if(a<b) return a;
else return b;
}
void bfs(){
while(!q.empty()){
int x=q.front();
q.pop();
for(int i=0;i<a[x].size();i++){
int y=a[x][i];
d[y]=maxi(d[y],d[x]+createtime[y]);
indegree[y]--;
if(indegree[y]==0){
q.push(y);
}
}
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int test;
cin >> test;
for(int t=0;t<test;t++){
memset(d,0,sizeof(d));
memset(createtime,0,sizeof(createtime));
memset(indegree,0,sizeof(indegree));
ans=0;
for(int i=0;i<1001;i++){
a[i].clear();
}
int n,k,victory;
cin >> n >> k;
for(int i=1;i<n+1;i++){
cin >> createtime[i];
}
for(int i=1;i<k+1;i++){
int x,y;
cin >> x >> y;
a[x].push_back(y);
indegree[y]++;
}
cin >> victory;
for(int i=1;i<n+1;i++){
if(indegree[i]==0){
d[i]=createtime[i];
q.push(i);
}
}
bfs();
cout << d[victory] << "\n";
}
}
반응형
'Algorithm > Graph' 카테고리의 다른 글
[Graph] 합승 택시 요금 - 2021 KAKAO BLIND RECRUITMENT (0) | 2022.09.28 |
---|---|
[그래프, 난이도 중] 프로그래머즈, 순위 (0) | 2020.10.08 |
[그래프, 난이도 중] 프로그래머즈, 가장 먼 노드 (0) | 2020.10.07 |
[SCC, 난이도 중상] 백준 9466번 텀 프로젝트 (0) | 2020.08.15 |
댓글