문제 정의
- 일부 노드들의 순서가 주어졌을때, 전체 순서를 정하는 문제
문제 접근
- 노드 순서를 인접 리스트(adj)로 저장
- 인접 리스트로 저장하면서, 노드에 들어오는 간선의 개수(indeg)를 기록
- 큐를 하나 생성해서, indeg가 0인 것들을 추가
- indeg가 0이란 의미 : 들어오는 간선이 없으므로, 출발노드
- 각 큐에 들어있는 노드에 대해서 다음을 반복
- 결과 리스트에 추가
- 각 노드에 인접한 노드들에 대해, indeg를 감소
- 이떄, indeg가 0인 노드는 큐에 새로 추가
- 결과 리스트 출력
시간복잡도
- 모든 노드 : V
- 모든 노드에 인접한 노드의 indeg 감소 : E
- O(V + E)
인트 계산
- 모든 입력 >> 10억 이하의정음수 >> INT 가능
- dp값 : 최악의 케이스는 약 4^2500? >> 안전하게 LL 사용
대표예제 : 백준 2252 줄세우기
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 | #include <iostream> #include <queue> #include <vector> using namespace std; // 각 노드의 인접 리스트 vector<int> adj[32010]; // 각 노드에 들어오는 간선 개수 int indeg[32010]; int main() { ios::sync_with_stdio(0); cin.tie(0); int N,M; cin >> N >> M; for(int i=0; i<M; i++) { int a,b; cin >> a >> b; // 인접한 간선 추가 adj[a].push_back(b); // 들어오는 간선의 개수 증가 indeg[b]++; } queue<int> q; for(int i=1; i<=N; i++) { if(indeg[i]==0) q.push(i); } vector<int> rs; while(!q.empty()) { int eq = q.front(); q.pop(); rs.push_back(eq); for(int x : adj[eq]) { // 들어오는 간선의 개수 감소 indeg[x]--; // 만약 들어오는 간선의 개수가 0일때 큐에 추가 if(indeg[x] == 0) q.push(x); } } for(int ers : rs) cout << ers << ' '; return 0; } | cs |
비슷한 유형
- 몇번째 순서인지 구하는 문제
- topological sort는 전체 순서는 맞지만, 내가 몇번째 순서인지 정확히 알수는 없음
- 예시 : 1번 노드가 2번쨰 순서도 정답이고 3번째 순서도 정답임
- 즉, 순서가 뒤틀리거나 틀리지만 않으면 됨
- 내가 정확히 몇번째 순서를 구하는 문제는 플로이드를 통해서 확인 가능
- https://www.acmicpc.net/problem/2458
- map[j][k] = 1 && map[k][i] ==1 >> map[j][i] =1
- topological sort는 전체 순서는 맞지만, 내가 몇번째 순서인지 정확히 알수는 없음
'알고리즘 > 개념' 카테고리의 다른 글
[알고리즘] Dijkstra, 다익스트라 알고리즘 (0) | 2021.02.14 |
---|---|
[알고리즘] Floyd Warshall, 플로이드 와샬 알고리즘 (0) | 2021.02.08 |
[알고리즘] Minimum Spanning Tree, 최소 스패닝 트리 (0) | 2021.02.08 |
[알고리즘] 문자열 KMP, Rabin Karp (0) | 2021.02.07 |
[알고리즘] 문자열 TRIE (0) | 2021.02.07 |