/* 위상정렬이 무엇인가요. 어떤 노드를 방문할 때 반드시 선행 노드가 이미 모두 방문되어야 하는 조건을 만족하는 노드 방문 순서를 결정하는 정렬입니다. 위상 정렬 기초에서. 위상 정렬 순서대로 노드를 방문하면서 후행 노드의 최소건설시간을 갱신하면 됩니다. 빈 노드에서 큐를 꺼내서 처리하는 과정입니다. 1번 노드의 후행자인 2,3 번 노드이 최소 건설시간을 갱신합니다. 2번 노드를 꺼내서 처리하고, 4,5번 노드가 큐에 새로 들어옵니다. 오께이요. 번 노드를 꺼내고 6번 노드가 새로 들어갑니다. */ #include <cstdio> #include <vector> #include <queue> #include <algorithm> #include <iostream> using namespace std; int main() { int T; cin >> T; for (int t = 0; t < T; t++) { int N, K, W, time[1000], pre[1000] = { 0 }; vector<int> suc[1000]; cin >> N >> K; for (int i = 0; i < N; i++) cin >> time[i]; for (int i = 0; i < K; i++) { int X, Y; cin >> X >> Y; suc[X - 1].push_back(Y - 1); pre[Y - 1]++; } cin >> W; W--; int result[1000] = { 0 }; queue<int> Q; for (int i = 0; i < N; i++) if (!pre[i]) Q.push(i); while (pre[W] > 0) { int u = Q.front(); Q.pop(); for (int next : suc[u]) { result[next] = max(result[next], result[u] + time[u]); if (--pre[next] == 0) Q.push(next); } } cout << result[W] * time[W] << endl; } } |
백준 위상정렬 문제를 명확히 파악하고, 인풋이 많으므로 이것을 어떻게 받고 어떻게 처리할 것인지 구분합니다. 오께이. 그리고 벡터를 여러개 받을 수 있습니다. vector<int> suc[3] 이게 무슨 뜻인가요. 벡터가 3개인가요 아니면 어레이가 3개인가요. 아 저렇게 하면 2차원 처럼 사용이 가능합니다. 벡터 저장만 하고 |
벡터 어레이를 사용해서 하나의 노드를 만들어서 문제를 풀이합니다. 오케이요. 이것이 DFS 를 보고 다시 돌아오도록 하겠습니다. |