C++로 확인하는 주어진 종속성 조건에서 모든 작업 완료 가능 여부

이 글에서는 주어진 선행 조건(종속성)을 바탕으로 모든 작업을 완료할 수 있는지 확인하는 C++ 프로그램을 살펴보겠습니다.

예를 들어 세 개의 작업이 있고, 선행 조건이 [[1, 0], [2, 1], [3, 2]]로 주어졌다고 가정해 보겠습니다.

([1, 0]은 작업 '1'을 수행하려면 먼저 작업 '0'을 완료해야 한다는 의미입니다.)

이 예제에서 작업 '0'은 선행 조건이 없으므로 가장 먼저 완료할 수 있습니다. 작업 '0'이 끝났으므로 이어서 작업 '1'을 완료할 수 있고, 같은 방식으로 작업 '2'와 '3'도 차례대로 완료할 수 있습니다. 따라서 이 경우의 답은 "True"입니다.

접근 방법: 그래프와 DFS 활용

이 문제는 그래프 알고리즘으로 해결할 수 있습니다. 배열은 그래프 알고리즘에 적합하지 않기 때문에, 먼저 입력을 그래프 형태로 변환해야 합니다. 작업 'n'이 작업 'm'의 완료에 의존한다면, 작업 'm'에서 작업 'n'으로 향하는 간선을 추가하는 방식으로 그래프를 구성할 수 있습니다.

그래프가 완성되면 DFS(깊이 우선 탐색)를 적용합니다. 특정 노드에서 출발해 인접한 노드를 방문하고, 다시 그 노드의 인접 노드를 방문하는 식으로 탐색을 깊게 진행합니다. 이 과정에서 이미 방문 중인 노드를 다시 만나게 되면 사이클(cycle)이 존재한다는 뜻이며, 이 경우 "False"를 반환합니다. 반대로 말단 노드에 도달하면 다른 노드에서도 동일한 패턴으로 탐색을 이어가 그래프의 모든 노드를 방문하고, 모든 노드를 문제없이 순회했다면 "True"를 반환합니다.

핵심 원리는 간단합니다. 종속성 관계에 사이클이 존재하면 해당 작업들은 서로를 무한히 기다리게 되어 어떤 작업도 시작할 수 없습니다. 즉, 사이클이 하나라도 있으면 모든 작업을 완료할 수 없고, 사이클이 전혀 없다면 모든 작업을 완료할 수 있습니다.

예제 코드

#include <bits/stdc++.h>
using namespace std;
// 의존성 목록을 그래프로 변환
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;
}
// 사이클 존재 여부 확인 (DFS)
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;
}
// 모든 작업을 완료할 수 있는지 확인
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;
}

코드 설명

make_graph 함수: 의존성 목록(pair 배열)을 인접 리스트 형태의 그래프로 변환합니다. 각 의존성 쌍 (a, b)에 대해 b → a 방향의 간선을 추가하여, b를 먼저 완료해야 a를 수행할 수 있다는 관계를 표현합니다.

cycle 함수: DFS를 수행하며 사이클을 감지합니다. onway 배열은 현재 탐색 경로 위에 있는 노드를 추적하고, visited 배열은 한 번이라도 방문한 노드를 기록합니다. 탐색 경로상의 노드(onway가 true인 노드)를 다시 만나면 사이클이 존재하는 것이므로 true를 반환합니다.

canFinish 함수: 모든 작업을 순회하며 아직 방문하지 않은 노드에 대해 cycle 함수를 호출합니다. 어느 하나라도 사이클이 발견되면 false를 반환하고, 모든 노드를 안전하게 탐색했다면 true를 반환합니다.

출력 결과

True

위 예제에서는 6개의 작업과 5개의 의존성이 주어졌으며, 의존성 체인이 0 → 1 → 2 → 3 → 5 → 4 순서의 선형 구조를 이루고 있어 사이클이 없습니다. 따라서 모든 작업을 완료할 수 있으므로 "True"가 출력됩니다.

이 알고리즘의 시간 복잡도는 노드 수를 V, 간선 수를 E라 할 때 O(V + E)이며, 공간 복잡도 역시 그래프 저장과 방문 배열 때문에 O(V + E)입니다. 이는 강의 이수 순서 검증이나 빌드 시스템의 의존성 분석 등 실제 다양한 문제에 응용될 수 있는 대표적인 위상 정렬 기반 기법입니다.