0x1A. 위상 정렬(Topological Sort) 알고리즘

0x1A 위상 정렬

0x00 위상 정렬의 정의

위상 정렬 : 방향 그래프에서 간선으로 주어진 정점 간 선후관계를 위배하지 않도록 나열하는 정렬

만약 그래프 내에 사이클이 존재할 경우에는 올바른 위상 정렬이 존재할 수 없다.

그렇기에 위상 정렬은 사이클이 존재하지 않는 방향 그래프에서만 잘 정의된다. 사이클이 존재하지 않는 방향 그래프를 **DAG(Directed Acyclic Graph)**라고 줄여서 부르기도 한다.

0x01 알고리즘 구현

구현 편의를 위한 성질

1. 정점과 간선을 실제로 지울 필요 없이 미리 indegree의 값을 저장했다가 매번 뻗어나가는 정점들의 indegree 값만 1 감소시켜도 과정을 수행 가능
2. indegree가 0인 정점을 구하기 위해 매번 모든 정점들을 다 확인하는 대신 목록을 따로 저장하고 있다가 직전에 제거한 정점에서 연결된 정점들만 추가 -> Queue 사용

알고리즘 순서

1. 맨 처음 모든 간선을 읽으며 indegree 테이블을 채움
2. Indegree가 0인 정점들을 모두 큐에 넣음
3. 큐에서 정점을 꺼내어 위상 정렬 결과에 추가
4. 해당 정점으로부터 연결된 모든 정점의 indegree 값을 1 감소시킴. 이 때 indegree가 0이 되었다면 그 정점을 큐에 추가
5. 큐가 빌 때까지 3, 4번 과정을 반복

vector<int> adj[10];
int deg[10];
int n;

queue<int> q;
vector<int> result;
for(int i=1; i<=n; i++)
	if(deg[i]= 0) q.push(i);
while(!q.empty()) {
	int cur= q.front(); q.pop();
    result.push_back(cur);
    for(int nxt : adj[cur]) {
    	deg[nxt]--;
        if(deg[nxt]= 0) q.push(nxt);
    }
}
if(result.size() = n)
	cout << "cycle exists";
else {
	for(auto x : result) cout << x << ' ';
}

0x02 연습문제 1 - BOJ 2252번 : 줄 세우기

int n, m;
vector<int> adj[32002];
int deg[32002];

int main() {
    cin >> n >> m;
    for(int i=0; i<m; i++) {
        int a, b;
        cin >> a >> b;
        adj[a].push_back(b);
        deg[b]++;
    }

    queue<int> q;
    vector<int> ans;
    for(int i=1 ;i<=n; i++)
        if(deg[i]= 0) q.push(i);
    while(!q.empty()) {
        int cur= q.front(); q.pop();
        ans.push_back(cur);
        for(int nxt : adj[cur]) {
            deg[nxt]--;
            if(deg[nxt]= 0) q.push(nxt);
        }
    }

    if(ans.size() = n) cout << "cycle" << endl;
    else for(int i : ans) cout << i << " ";
    cout << endl;

    return 0;
}

문제 풀이

Note_ 21276 계보 복원가 호석 : find_index 함수를 정의해서 이름에 index를 매핑하려고 했지만 O(N)이 걸려서 시간초과가 났다. Hash map(map)으로 관리하면 이름을 인덱스로 바꾸는게 O(1)에 가능하게 된다는 것을 알았다.

map<key, value>

map<string, int> name_to_index;

// 이름을 인덱스로 매핑
for (int i = 0; i < n; i++)
    name_to_index[name[i]]= i;

cin >> m;
for (int i = 0; i < m; i++) {
    string a, b;
    cin >> a >> b;
    adj[name_to_index[b]].push_back(name_to_index[a]);
    deg[name_to_index[a]]++;
}

1766 문제집 : queue에서 정렬이 필요해서 priority queue를 이용해서 풀이하였다

priority_queue<int, vector<int>, greater<int>> q;

리뷰

출처: 바킹독님의 실전알고리즘 강의