n개의 서로 다른 작업이 있다고 가정해 보겠습니다. 각 작업에는 0부터 n-1까지 번호가 붙어 있으며, 일부 작업은 반드시 먼저 완료해야 하는 선행 작업(prerequisite)을 가질 수 있습니다. 예를 들어 [2, 1]이라는 쌍은 "작업 2를 수행하려면 먼저 작업 1을 끝내야 한다"는 의미입니다.
전체 작업의 개수와 선행 관계 쌍의 목록이 주어졌을 때, 모든 작업을 완료할 수 있는 순서를 찾아야 합니다. 올바른 순서가 여러 개 존재한다면 그중 하나만 반환하면 되며, 모든 작업을 완료하는 것이 불가능한 경우(순환 종속성이 존재하는 경우)에는 빈 배열을 반환합니다.
예를 들어 입력이 n = 4, A = [[1, 0], [2, 0], [3, 2], [3, 1], [4, 2]]라면 출력은 [0, 2, 1, 4, 3]이 됩니다.
접근 방법: DFS 기반 위상 정렬
이 문제는 본질적으로 방향 그래프의 위상 정렬(Topological Sort) 문제와 같습니다. DFS(깊이 우선 탐색)로 그래프를 탐색하면서 사이클의 존재 여부를 함께 검사하고, 사이클이 없다면 탐색 과정에서 얻은 역방향 순서를 뒤집어 최종 작업 순서를 구할 수 있습니다.
알고리즘 단계
- dfs() 함수를 정의합니다. 이 함수는 그래프(graph), 시작 노드(start), 경로 표시 배열(onpath), 방문 배열(visited), 위상 정렬 결과 배열(toposort)을 매개변수로 받습니다.
- visited[start]가 이미 방문 처리되어 있다면 false를 반환합니다.
- onpath[start]와 visited[start]를 true로 설정합니다.
- graph[start]의 각 이웃(neighbor)에 대해 다음을 수행합니다.
- onpath[neighbor]가 true이거나 dfs(graph, neighbor, onpath, visited, toposort)의 결과가 true라면 true를 반환합니다. 이는 현재 탐색 경로 안에서 다시 자기 자신에게 돌아왔다는 뜻으로, 사이클이 존재함을 의미합니다.
- 사이클이 아니라면 start를 toposort의 끝에 추가합니다.
- onpath[start]를 false로 되돌린 후 반환합니다.
메인 함수에서는 다음과 같이 진행합니다.
- pre 배열에 저장된 간선 정보를 바탕으로 n개의 정점을 가진 그래프를 생성합니다.
- toposort 배열을 선언합니다.
- 크기가 n인 onpath 배열을 선언하고 false로 초기화합니다.
- 크기가 n인 visited 배열을 선언하고 false로 초기화합니다.
- i를 0부터 n-1까지 1씩 증가시키며 다음을 반복합니다.
- visited[i]가 false이면서 dfs(graph, i, onpath, visited, toposort)가 true를 반환하면(사이클 발견) 빈 배열을 반환합니다.
- 모든 정점을 문제없이 탐색했다면 toposort 배열을 뒤집습니다.
- toposort를 반환합니다.
예제 코드
다음 구현을 통해 더 잘 이해해 보겠습니다.
#include <bits/stdc++.h>
using namespace std;
vector<unordered_set<int> > create_graph(int n, vector<pair<int, int> >& pre) {
vector<unordered_set<int> > graph(n);
for (auto pre : pre)
graph[pre.second].insert(pre.first);
return graph;
}
bool dfs(vector<unordered_set<int> >& graph, int start,vector<bool>& onpath, vector<bool>& visited, vector<int>& toposort) {
if (visited[start])
return false;
onpath[start] = visited[start] = true;
for (int neigh : graph[start])
if (onpath[neigh] || dfs(graph, neigh, onpath, visited, toposort))
return true;
toposort.push_back(start);
return onpath[start] = false;
}
vector<int> get_order(int n, vector<pair<int, int> > &pre){
vector<unordered_set<int> > graph = create_graph(n, pre);
vector<int> toposort;
vector<bool> onpath(n, false), visited(n, false);
for (int i = 0; i < n; i++)
if (!visited[i] && dfs(graph, i, onpath, visited, toposort))
return {};
reverse(toposort.begin(), toposort.end());
return toposort;
}
int main() {
int n = 4;
vector<pair<int, int> > pre = {{1, 0}, {2, 0}, {3, 2}, {3, 1},{4,0}};
vector<int> v = get_order(n, pre);
for (int i = 0; i < v.size(); i++) {
cout << v[i] << " ";
}
}
입력
4, {{1, 0}, {2, 0}, {3, 2}, {3, 1},{4,0}}
출력
0 1 4 2 3