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;

리뷰

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