1005 풀이
※ 문제 링크 : https://www.acmicpc.net/problem/1005
이 문제는 위상 정렬(topological sorting)1을 사용하는 문제입니다. 저는 이 문제의 풀이를 총 3단계로 나누어서 풀었습니다. 먼저 아래와 같이 테스트 케이스가 여러 개이므로 main을 다음과 같이 구축을 해주도록 합니다.
int main(){
ios::sync_with_stdio(false); cin.tie(NULL);
int T; cin >> T;
for(int i = 0 ; i < T; i++)
run();
return 0;
}
이번 문제의 경우 입력 값이 많으므로 ios::sync_with_stdio(false);, cin.tie(NULL)2을 실시해주도록 합니다. 그리고 각 테스트마다 독립적으로 모듈들이 돌아갈 수 있도록 run()이라는 함수를 만들었습니다.
그리고 각 테스트 케이스에 대한 run()의 구현은 아래와 같이 됩니다.
void run(){
int N, K, D;
cin >> N >> K;
vector<int> T(N+1, INF);
Graph adj;
for(int i = 1; i <= N ; i++)
cin >> T[i];
for(int i = 0; i < K; i++){
int src, dst; cin >> src >> dst;
adj[src].push_back(dst);
}
cin >> D;
vector<int> seq;
topoSort(adj, N, seq);
cout << traverse(adj, seq, T, D) << endl;
}
문제 조건에서 노드의 수 N, 연결 관련 수 K, 도착 지점 D로 구성된다 하였으므로 3개의 변수를 만들어주고, 추가적으로 노드의 가중치(시간)를 저장하는 T와 그래프의 연결 상태를 저장할 인접 리스트 adj를 구성하도록 합니다. 그리고 각각의 데이터를 주어진 조건에 맡게 받도록 하고, 위상 정렬의 결과를 저장할 seq 리스트를 만들도록 합니다. 이 후, 위상 정렬을 수행하고 순회를 하여 결과 값을 받아내도록 합니다.
이 때, 위상 정렬은 아래와 같이 만들어집니다.
void topoSort(Graph& adj, const int& N, vector<int>& seq){
stack<Node> st;
stack<int> order;
vector<bool> visited(N+1, false);
for(int i = 1; i <= N; i++){
if(visited[i] == false){
st.push({false, i});
}
while(!st.empty()){
Node cur = st.top();
st.pop();
if(cur.isParent){
order.push(cur.num);
continue;
}
visited[cur.num] = true;
st.push({true, cur.num});
for(const auto &next : adj[cur.num]){
if(visited[next] == false){
st.push({false, next});
}
} // end of for
} // end of while
} // end of for
while(!order.empty()){
seq.push_back(order.top());
order.pop();
}
}
위상정렬을 구현할 때 익히 알려진 재귀적 용법을 사용하지 않고 반복문을 사용해서 제작3을 하였습니다. 이 결과 만들어진 결과를 seq 리스트에 넣어주도록 합니다.
이렇게 넣어진 순서를 traverse 함수에 전달하여 아래와 같이 노드를 들리면서 확산하듯이 값을 더하도록 해주면 됩니다.
int traverse(Graph& adj,
const vector<int>& seq,
const vector<int>& time,
const int& D){
//cout << time.size() << endl;
vector<int> result(time.size(), -1);
for(const auto& cur : seq){
if(result[cur] == -1)
result[cur] = time[cur];
for(const auto& next : adj[cur]){
result[next] = max(result[next], result[cur] + time[next]);
}
}
return result[D];
}
이런 식으로 해서 문제를 풀 수 있습니다. 결과적으로, 전체 코드는 다음과 같습니다.
#include<iostream>
#include<algorithm>
#include<unordered_map>
#include<vector>
#include<stack>
using namespace std;
#define INF 987654321
typedef unordered_map<int,vector<int>> Graph;
typedef struct _NODE{
bool isParent;
int num;
}Node;
void topoSort(Graph& adj, const int& N, vector<int>& seq){
stack<Node> st;
stack<int> order;
vector<bool> visited(N+1, false);
for(int i = 1; i <= N; i++){
if(visited[i] == false){
st.push({false, i});
}
while(!st.empty()){
Node cur = st.top();
st.pop();
if(cur.isParent){
order.push(cur.num);
continue;
}
visited[cur.num] = true;
st.push({true, cur.num});
for(const auto &next : adj[cur.num]){
if(visited[next] == false){
st.push({false, next});
}
} // end of for
} // end of while
} // end of for
while(!order.empty()){
seq.push_back(order.top());
order.pop();
}
}
int traverse(Graph& adj,
const vector<int>& seq,
const vector<int>& time,
const int& D){
//cout << time.size() << endl;
vector<int> result(time.size(), -1);
for(const auto& cur : seq){
if(result[cur] == -1)
result[cur] = time[cur];
for(const auto& next : adj[cur]){
result[next] = max(result[next], result[cur] + time[next]);
}
}
return result[D];
}
void run(){
int N, K, D;
cin >> N >> K;
vector<int> T(N+1, INF);
Graph adj;
for(int i = 1; i <= N ; i++)
cin >> T[i];
for(int i = 0; i < K; i++){
int src, dst; cin >> src >> dst;
adj[src].push_back(dst);
}
cin >> D;
vector<int> seq;
topoSort(adj, N, seq);
cout << traverse(adj, seq, T, D) << endl;
}
int main(){
ios::sync_with_stdio(false); cin.tie(NULL);
int T; cin >> T;
for(int i = 0 ; i < T; i++)
run();
return 0;
}