13_topological_sort.cpp

Download
cpp 417 lines 11.2 KB 
  1/*
  2 * μœ„μƒ μ •λ ¬ (Topological Sort)
  3 * Kahn's Algorithm, DFS-based, Cycle Detection
  4 *
  5 * DAG(Directed Acyclic Graph)μ—μ„œ μ •μ λ“€μ˜ μ„ ν˜• μˆœμ„œλ₯Ό μ°ΎμŠ΅λ‹ˆλ‹€.
  6 */
  7
  8#include <iostream>
  9#include <vector>
 10#include <queue>
 11#include <stack>
 12#include <algorithm>
 13
 14using namespace std;
 15
 16// =============================================================================
 17// 1. Kahn's Algorithm (BFS 기반)
 18// =============================================================================
 19
 20vector<int> topologicalSortKahn(int n, const vector<vector<int>>& adj) {
 21    vector<int> indegree(n, 0);
 22
 23    // μ§„μž… 차수 계산
 24    for (int u = 0; u < n; u++) {
 25        for (int v : adj[u]) {
 26            indegree[v]++;
 27        }
 28    }
 29
 30    // μ§„μž… μ°¨μˆ˜κ°€ 0인 정점을 큐에 μΆ”κ°€
 31    queue<int> q;
 32    for (int i = 0; i < n; i++) {
 33        if (indegree[i] == 0) {
 34            q.push(i);
 35        }
 36    }
 37
 38    vector<int> result;
 39    while (!q.empty()) {
 40        int node = q.front();
 41        q.pop();
 42        result.push_back(node);
 43
 44        for (int neighbor : adj[node]) {
 45            indegree[neighbor]--;
 46            if (indegree[neighbor] == 0) {
 47                q.push(neighbor);
 48            }
 49        }
 50    }
 51
 52    // 사이클이 있으면 λͺ¨λ“  정점을 λ°©λ¬Έν•  수 μ—†μŒ
 53    if ((int)result.size() != n) {
 54        return {};  // 사이클 쑴재
 55    }
 56
 57    return result;
 58}
 59
 60// =============================================================================
 61// 2. DFS 기반 μœ„μƒ μ •λ ¬
 62// =============================================================================
 63
 64void topoDFS(int node, const vector<vector<int>>& adj,
 65             vector<bool>& visited, stack<int>& st) {
 66    visited[node] = true;
 67
 68    for (int neighbor : adj[node]) {
 69        if (!visited[neighbor]) {
 70            topoDFS(neighbor, adj, visited, st);
 71        }
 72    }
 73
 74    st.push(node);
 75}
 76
 77vector<int> topologicalSortDFS(int n, const vector<vector<int>>& adj) {
 78    vector<bool> visited(n, false);
 79    stack<int> st;
 80
 81    for (int i = 0; i < n; i++) {
 82        if (!visited[i]) {
 83            topoDFS(i, adj, visited, st);
 84        }
 85    }
 86
 87    vector<int> result;
 88    while (!st.empty()) {
 89        result.push_back(st.top());
 90        st.pop();
 91    }
 92
 93    return result;
 94}
 95
 96// =============================================================================
 97// 3. 사이클 탐지 (DFS)
 98// =============================================================================
 99
100bool hasCycleDFS(int node, const vector<vector<int>>& adj,
101                 vector<int>& color) {
102    color[node] = 1;  // λ°©λ¬Έ 쀑 (νšŒμƒ‰)
103
104    for (int neighbor : adj[node]) {
105        if (color[neighbor] == 1) {
106            return true;  // λ°± 엣지 발견 (사이클)
107        }
108        if (color[neighbor] == 0 && hasCycleDFS(neighbor, adj, color)) {
109            return true;
110        }
111    }
112
113    color[node] = 2;  // λ°©λ¬Έ μ™„λ£Œ (검은색)
114    return false;
115}
116
117bool hasCycle(int n, const vector<vector<int>>& adj) {
118    vector<int> color(n, 0);  // 0: λ―Έλ°©λ¬Έ, 1: λ°©λ¬Έ 쀑, 2: μ™„λ£Œ
119
120    for (int i = 0; i < n; i++) {
121        if (color[i] == 0 && hasCycleDFS(i, adj, color)) {
122            return true;
123        }
124    }
125
126    return false;
127}
128
129// =============================================================================
130// 4. λͺ¨λ“  μœ„μƒ μ •λ ¬ μˆœμ„œ μ°ΎκΈ°
131// =============================================================================
132
133void allTopoSorts(vector<vector<int>>& adj, vector<int>& indegree,
134                  vector<int>& result, vector<bool>& visited,
135                  vector<vector<int>>& allResults, int n) {
136    bool found = false;
137
138    for (int i = 0; i < n; i++) {
139        if (indegree[i] == 0 && !visited[i]) {
140            // 이 정점 선택
141            visited[i] = true;
142            result.push_back(i);
143
144            for (int neighbor : adj[i]) {
145                indegree[neighbor]--;
146            }
147
148            allTopoSorts(adj, indegree, result, visited, allResults, n);
149
150            // λ°±νŠΈλž˜ν‚Ή
151            visited[i] = false;
152            result.pop_back();
153            for (int neighbor : adj[i]) {
154                indegree[neighbor]++;
155            }
156
157            found = true;
158        }
159    }
160
161    if (!found && (int)result.size() == n) {
162        allResults.push_back(result);
163    }
164}
165
166vector<vector<int>> findAllTopologicalSorts(int n, const vector<vector<int>>& adj) {
167    vector<int> indegree(n, 0);
168    for (int u = 0; u < n; u++) {
169        for (int v : adj[u]) {
170            indegree[v]++;
171        }
172    }
173
174    vector<int> result;
175    vector<bool> visited(n, false);
176    vector<vector<int>> allResults;
177    vector<vector<int>> adjCopy = adj;
178
179    allTopoSorts(adjCopy, indegree, result, visited, allResults, n);
180
181    return allResults;
182}
183
184// =============================================================================
185// 5. κ³Όλͺ© μˆ˜κ°• μˆœμ„œ (Course Schedule)
186// =============================================================================
187
188bool canFinish(int numCourses, vector<pair<int, int>>& prerequisites) {
189    vector<vector<int>> adj(numCourses);
190    vector<int> indegree(numCourses, 0);
191
192    for (auto& [course, prereq] : prerequisites) {
193        adj[prereq].push_back(course);
194        indegree[course]++;
195    }
196
197    queue<int> q;
198    for (int i = 0; i < numCourses; i++) {
199        if (indegree[i] == 0) {
200            q.push(i);
201        }
202    }
203
204    int count = 0;
205    while (!q.empty()) {
206        int node = q.front();
207        q.pop();
208        count++;
209
210        for (int neighbor : adj[node]) {
211            indegree[neighbor]--;
212            if (indegree[neighbor] == 0) {
213                q.push(neighbor);
214            }
215        }
216    }
217
218    return count == numCourses;
219}
220
221vector<int> findOrder(int numCourses, vector<pair<int, int>>& prerequisites) {
222    vector<vector<int>> adj(numCourses);
223    vector<int> indegree(numCourses, 0);
224
225    for (auto& [course, prereq] : prerequisites) {
226        adj[prereq].push_back(course);
227        indegree[course]++;
228    }
229
230    queue<int> q;
231    for (int i = 0; i < numCourses; i++) {
232        if (indegree[i] == 0) {
233            q.push(i);
234        }
235    }
236
237    vector<int> result;
238    while (!q.empty()) {
239        int node = q.front();
240        q.pop();
241        result.push_back(node);
242
243        for (int neighbor : adj[node]) {
244            indegree[neighbor]--;
245            if (indegree[neighbor] == 0) {
246                q.push(neighbor);
247            }
248        }
249    }
250
251    if ((int)result.size() != numCourses) {
252        return {};
253    }
254
255    return result;
256}
257
258// =============================================================================
259// 6. 외계인 사전 (Alien Dictionary)
260// =============================================================================
261
262string alienOrder(vector<string>& words) {
263    // κ·Έλž˜ν”„ ꡬ성
264    unordered_map<char, unordered_set<char>> adj;
265    unordered_map<char, int> indegree;
266
267    // λͺ¨λ“  문자 μ΄ˆκΈ°ν™”
268    for (const string& word : words) {
269        for (char c : word) {
270            if (indegree.find(c) == indegree.end()) {
271                indegree[c] = 0;
272            }
273        }
274    }
275
276    // μΈμ ‘ν•œ 단어 λΉ„κ΅ν•˜μ—¬ μˆœμ„œ κ²°μ •
277    for (int i = 0; i < (int)words.size() - 1; i++) {
278        string& w1 = words[i];
279        string& w2 = words[i + 1];
280
281        // 잘λͺ»λœ μˆœμ„œ 체크 (prefixκ°€ 더 뒀에 올 수 μ—†μŒ)
282        if (w1.length() > w2.length() &&
283            w1.substr(0, w2.length()) == w2) {
284            return "";
285        }
286
287        for (int j = 0; j < (int)min(w1.length(), w2.length()); j++) {
288            if (w1[j] != w2[j]) {
289                if (adj[w1[j]].find(w2[j]) == adj[w1[j]].end()) {
290                    adj[w1[j]].insert(w2[j]);
291                    indegree[w2[j]]++;
292                }
293                break;
294            }
295        }
296    }
297
298    // μœ„μƒ μ •λ ¬
299    queue<char> q;
300    for (auto& [c, deg] : indegree) {
301        if (deg == 0) {
302            q.push(c);
303        }
304    }
305
306    string result;
307    while (!q.empty()) {
308        char c = q.front();
309        q.pop();
310        result += c;
311
312        for (char next : adj[c]) {
313            indegree[next]--;
314            if (indegree[next] == 0) {
315                q.push(next);
316            }
317        }
318    }
319
320    if (result.length() != indegree.size()) {
321        return "";  // 사이클 쑴재
322    }
323
324    return result;
325}
326
327// =============================================================================
328// ν…ŒμŠ€νŠΈ
329// =============================================================================
330
331void printVector(const vector<int>& v) {
332    cout << "[";
333    for (size_t i = 0; i < v.size(); i++) {
334        cout << v[i];
335        if (i < v.size() - 1) cout << ", ";
336    }
337    cout << "]";
338}
339
340int main() {
341    cout << "============================================================" << endl;
342    cout << "μœ„μƒ μ •λ ¬ 예제" << endl;
343    cout << "============================================================" << endl;
344
345    // ν…ŒμŠ€νŠΈ κ·Έλž˜ν”„
346    //   5 β†’ 0 ← 4
347    //   ↓       ↓
348    //   2 β†’ 3 β†’ 1
349    int n = 6;
350    vector<vector<int>> adj(n);
351    adj[5] = {0, 2};
352    adj[4] = {0, 1};
353    adj[2] = {3};
354    adj[3] = {1};
355
356    // 1. Kahn's Algorithm
357    cout << "\n[1] Kahn's Algorithm (BFS)" << endl;
358    auto result1 = topologicalSortKahn(n, adj);
359    cout << "    μœ„μƒ μ •λ ¬: ";
360    printVector(result1);
361    cout << endl;
362
363    // 2. DFS 기반
364    cout << "\n[2] DFS 기반 μœ„μƒ μ •λ ¬" << endl;
365    auto result2 = topologicalSortDFS(n, adj);
366    cout << "    μœ„μƒ μ •λ ¬: ";
367    printVector(result2);
368    cout << endl;
369
370    // 3. 사이클 탐지
371    cout << "\n[3] 사이클 탐지" << endl;
372    cout << "    ν˜„μž¬ κ·Έλž˜ν”„: " << (hasCycle(n, adj) ? "사이클 있음" : "DAG") << endl;
373
374    vector<vector<int>> cycleAdj(3);
375    cycleAdj[0] = {1};
376    cycleAdj[1] = {2};
377    cycleAdj[2] = {0};
378    cout << "    사이클 κ·Έλž˜ν”„: " << (hasCycle(3, cycleAdj) ? "사이클 있음" : "DAG") << endl;
379
380    // 4. λͺ¨λ“  μœ„μƒ μ •λ ¬
381    cout << "\n[4] λͺ¨λ“  μœ„μƒ μ •λ ¬ μˆœμ„œ" << endl;
382    vector<vector<int>> smallAdj(4);
383    smallAdj[0] = {1, 2};
384    smallAdj[1] = {3};
385    smallAdj[2] = {3};
386    auto allSorts = findAllTopologicalSorts(4, smallAdj);
387    cout << "    κ·Έλž˜ν”„: 0β†’1β†’3, 0β†’2β†’3" << endl;
388    cout << "    κ°€λŠ₯ν•œ μˆœμ„œ: " << allSorts.size() << "개" << endl;
389    for (auto& order : allSorts) {
390        cout << "      ";
391        printVector(order);
392        cout << endl;
393    }
394
395    // 5. κ³Όλͺ© μˆ˜κ°• μˆœμ„œ
396    cout << "\n[5] κ³Όλͺ© μˆ˜κ°• μˆœμ„œ" << endl;
397    vector<pair<int, int>> prereqs = {{1, 0}, {2, 0}, {3, 1}, {3, 2}};
398    cout << "    κ³Όλͺ© 수: 4, μ„ μˆ˜κ³Όλͺ©: (1,0), (2,0), (3,1), (3,2)" << endl;
399    cout << "    μˆ˜κ°• κ°€λŠ₯: " << (canFinish(4, prereqs) ? "예" : "μ•„λ‹ˆμ˜€") << endl;
400    auto order = findOrder(4, prereqs);
401    cout << "    μˆ˜κ°• μˆœμ„œ: ";
402    printVector(order);
403    cout << endl;
404
405    // 6. λ³΅μž‘λ„ μš”μ•½
406    cout << "\n[6] λ³΅μž‘λ„ μš”μ•½" << endl;
407    cout << "    | μ•Œκ³ λ¦¬μ¦˜       | μ‹œκ°„λ³΅μž‘λ„ | κ³΅κ°„λ³΅μž‘λ„ |" << endl;
408    cout << "    |----------------|------------|------------|" << endl;
409    cout << "    | Kahn (BFS)     | O(V + E)   | O(V)       |" << endl;
410    cout << "    | DFS 기반       | O(V + E)   | O(V)       |" << endl;
411    cout << "    | λͺ¨λ“  μˆœμ„œ      | O(V! Γ— V)  | O(V)       |" << endl;
412
413    cout << "\n============================================================" << endl;
414
415    return 0;
416}