[알고리즘] Topological Sort, 위상정렬

문제 정의

• 일부 노드들의 순서가 주어졌을때, 전체 순서를 정하는 문제

문제 접근

• 노드 순서를 인접 리스트(adj)로 저장
  • 인접 리스트로 저장하면서, 노드에 들어오는 간선의 개수(indeg)를 기록
  • 큐를 하나 생성해서, indeg가 0인 것들을 추가
    • indeg가 0이란 의미 : 들어오는 간선이 없으므로, 출발노드
  • 각 큐에 들어있는 노드에 대해서 다음을 반복
    • 결과 리스트에 추가
    • 각 노드에 인접한 노드들에 대해, indeg를 감소
    • 이떄, indeg가 0인 노드는 큐에 새로 추가
  • 결과 리스트 출력

시간복잡도

• 모든 노드 : V
  • 모든 노드에 인접한 노드의 indeg 감소 : E
  • O(V + E)

인트 계산

• 모든 입력 >> 10억 이하의정음수 >> INT 가능
• dp값 : 최악의 케이스는 약 4^2500? >> 안전하게 LL 사용

대표예제 : 백준 2252 줄세우기

#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;
}
 

비슷한 유형

• 몇번째 순서인지 구하는 문제
  • topological sort는 전체 순서는 맞지만, 내가 몇번째 순서인지 정확히 알수는 없음
    • 예시 : 1번 노드가 2번쨰 순서도 정답이고 3번째 순서도 정답임
    • 즉, 순서가 뒤틀리거나 틀리지만 않으면 됨
  • 내가 정확히 몇번째 순서를 구하는 문제는 플로이드를 통해서 확인 가능
  • https://www.acmicpc.net/problem/2458
  • map[j][k] = 1 && map[k][i] ==1 >> map[j][i] =1