-
(라이님 블로그 대회 알고리즘 따라잡기 20) 위상 정렬(Topological Sort)PROGRAMMING/알고리즘 2024. 6. 18. 10:08
위상 정렬(Topological Sort) (수정: 2017-06-22)
안녕하세요. 이번에도 역시 그래프입니다. 그래프 아직 한창 남았어요. 이번에는 위상 정렬(topological so...
blog.naver.com
최소 스패닝 트리와 뭔가뭔가 비슷한 느낌의 알고리즘
그래프의 정점을 정렬하는 방법으로 선수과목이 있는 문제들에서 사용 가능한 알고리즘이다.
라이님의 백준 2623번 문제를 vector를 사용해서 약간만 바꿔보았다.
https://www.acmicpc.net/problem/2623
#include <cstdio> #include <vector> #include <queue> using namespace std; int main() { int N, M; scanf("%d %d", &N, &M); vector<vector<int>> adj(N); vector<int> indegree(N, 0); for (int i = 0; i < M; i++) { int K, prev, curr; scanf("%d", &K); if (K > 0) { scanf("%d", &prev); for (int j = 1; j < K; j++) { scanf("%d", &curr); indegree[curr - 1]++; adj[prev - 1].push_back(curr - 1); prev = curr; } } } queue<int> Q; vector<int> result; for (int i = 0; i < N; i++) { if (indegree[i] == 0) Q.push(i); } for (int i = 0; i < N; i++) { if (Q.empty()) { puts("0"); return 0; } int curr = Q.front(); Q.pop(); result[i] = curr + 1; for (int next : adj[curr]) if (--indegree[next] == 0) Q.push(next); } for (int i = 0; i < N; i++) printf("%d\n", result[i]); }
이건 라이님의 백준 1516번 풀이에서 array 생성 부분만 수정한 코드다.
https://www.acmicpc.net/problem/1516
#include <cstdio> #include <vector> #include <queue> #include <algorithm> using namespace std; int main() { int N; scanf("%d", &N); vector<int> time(N), result(N, 0), indegree(N, 0); vector<vector<int>> adj(N); queue<int> Q; for (int i = 0; i < N; i++) { scanf("%d", &time[i]); while (1) { int pre; scanf("%d", &pre); if (pre == -1) break; indegree[i]++; adj[pre - 1].push_back(i); } if (indegree[i] == 0) { result[i] = time[i]; Q.push(i); } } for (int i = 0; i < N; i++) { int curr = Q.front(); Q.pop(); for (int next : adj[curr]){ result[next] = max(result[next], result[curr] + time[next]); if (--indegree[next] == 0) Q.push(next); } } for (int i = 0; i < N; i++) printf("%d\n", result[i]); }
'PROGRAMMING > 알고리즘' 카테고리의 다른 글