이 기사에서는 주어진 전제 조건을 기반으로 주어진 모든 작업을 완료할 수 있는지 확인하는 프로그램에 대해 논의할 것입니다.
예를 들어, 세 가지 작업이 주어지고 전제 조건이 [[1, 0], [2, 1], [3, 2]]라고 가정해 보겠습니다.
( [1,0]은 '1' 작업을 선택하기 위해 '0' 작업을 먼저 완료해야 함을 의미합니다.)
그런 다음 이 예에서는 '0' 작업에 전제 조건이 없으므로 먼저 완료할 수 있습니다. 그러면 '0' 작업이 완료되었으므로 '1' 작업이 완료될 수 있습니다. 마찬가지로 '2'와 '3' 작업도 완료할 수 있습니다. 따라서 이 경우의 대답은 "True"가 됩니다.
이 문제는 그래프 알고리즘을 사용하여 해결할 수 있습니다. 배열은 그래프 알고리즘에서 편리하지 않으므로 그래프로 변환합니다. 태스크 'n'이 'm'의 완료로 종속성을 갖는 경우 태스크 'm'에서 태스크 'n'으로 엣지를 만들어 이를 수행할 수 있습니다.
그래프가 만들어지면 DFS를 사용할 수 있습니다. 그 점에서 우리는 특정 노드에서 시작하여 가장 가까운 노드를 방문한 다음 해당 노드에 가장 가까운 노드 등을 방문할 수 있습니다. 이전에 방문한 적이 있는 노드를 만나면 주기가 만들어지고 "False"를 반환합니다. 그렇지 않으면 일단 터미널에 도달하면 그래프의 모든 노드를 방문할 때까지 이 패턴을 다시 다른 노드가 따라옵니다. 모든 노드에 도달하면 "True"를 반환합니다.
예시
#include <bits/stdc++.h>
using namespace std;
// Converts list into graph
vector<unordered_set<int> > make_graph(int Tasks, vector<pair<int, int> >& dependencies) {
vector<unordered_set<int> > graph(Tasks);
for (auto pre : dependencies)
graph[pre.second].insert(pre.first);
return graph;
}
//to check if all the nodes are visited
bool cycle(vector<unordered_set<int> >& graph, int node, vector<bool>& onway, vector<bool>& visited) {
if (visited[node])
return false;
onway[node] = visited[node] = true;
for (int near : graph[node]) {
if (onway[near] || cycle(graph, near, onway, visited))
return true;
}
return onway[node] = false;
}
//to check if all the tasks can be completed
bool canFinish(int Tasks, vector<pair<int, int> >& dependencies) {
vector<unordered_set<int>>graph = make_graph(Tasks, dependencies);
vector<bool> onway(Tasks, false), visited(Tasks, false);
for (int i = 0; i < Tasks; i++) {
if (!visited[i] && cycle(graph, i, onway, visited))
return false;
}
return true;
}
int main() {
int Tasks = 6;
vector<pair<int, int >> dependencies;
dependencies.push_back(make_pair(1, 0));
dependencies.push_back(make_pair(2, 1));
dependencies.push_back(make_pair(3, 2));
dependencies.push_back(make_pair(5, 3));
dependencies.push_back(make_pair(4, 5));
if (canFinish(Tasks, dependencies)) {
cout << "True";
}
else {
cout << "False";
}
return 0;
} 출력
True