위상정렬

위상정렬

• 방향성을 가진 비순환 그래프에서만 사용이 가능
• 특정한 순서로 실행이 되어야하는 상황에 사용이 적합

 

위상정렬은 위에서 간단하게 설명한 것 처럼 특정한 순서로 실행이 되어야하는 상황에서 사용을 할때 사용을 하게 됩니다. 게임에서 예를 들어 보겠습니다.

 

요즘 유명한 게임이죠 리그오브 레전드라는 게임에서 피바라기 라는 아이템을 구매하기 위해 필요한 아이템 목록입니다.

BF 대검 + 롱소드 + 흡혈의 낫을 그래프로 나타내면

다음과 같이 나타낼 수 있게 됩니다.

 B.F 대검과 롱소드 그리고 흡혈의 낫은 피바라기를 가르키고 있고

롱소드는 흡혈의 낫을 가리키고 있습니다.

그 이유는 각각의 아이템들은 피바라기의 선행조건이 되기 때문입니다.

 그리고 피바라기를 구매후에는 다시 각각의 아이템으로 바꿀 수 없게 됩니다.

 

이를 통해 피바라기 아이템 구매의 구조는 방향성을 가지는 비순환 그래프 구조를 가진다는 것을 알 수 있고,

피바라기를 구매하기 위한 아이템들을 위상정렬을 통해 차례대로 정렬할 수 있게되는거죠

 

과정

1. 자기 자신을 가리키는 변이 없는 꼭짓점을 찾음.
2. 찾은 꼭짓점을 출력하고 출력한 꼭짓점과 그 꼭짓점에서 출발하는 변을 삭제
3. 아직 그래프에 꼭짓점이 남아있으면 단계 1로 돌아가고, 아니면 알고리즘을 종료시킨다.

위의 과정은 위키 백과에의 위상정렬의 수행과정입니다.

https://ko.wikipedia.org/wiki/%EC%9C%84%EC%83%81%EC%A0%95%EB%A0%AC

위상정렬 - 위키백과, 우리 모두의 백과사전

여기서 한 꼭지점에서 자신을 가르키는 변의 개수를 진입차수이라고 부르고 자신이 가르키는 변의 개수를 진출차수라는 표현을 합니다.

 

위키백과의 정렬 과정을 다시 정리해보면

1. 진입차수가 0인 꼭지점에서 시작하여 해당 꼭지점에서 연결되어 있는
2. 꼭지점의 진입차수를 삭제한다
3. 진입차수가 남아 있는 꼭지점이 남아 있다면 1단계로 돌아가고 아닐경우 알고리즘을 종료한다.

※진입차수가 0인 꼭지점은 큐에 넣어 관리를 하도록 하겠습니다.

 

다시 정리한 내용을 아래의 그래프를 예시로 과정설명을 하도록 하겠습니다.

진입차수

1 : 0개

2 : 1개

3 : 2개

4 : 0개

5 : 0개

6 : 2개

 

전입차수가 0인 1, 4, 5를 큐에 넣음

큐에 있는 1을 꺼내어 1번 과정인 2의 전입차수를 삭제

과정 3의 조건을 만족하지 못하기 때문에 다시 1로 돌아가서 수행

전입차수가 0이된 2를 큐에 넣음

이 과정을 반복하면

 

 

 

 

큐에 쌓여 있던 값을 순서대로 출력하면 1 4 5 2 3 6 순으로 정렬되게 됩니다.

큐뿐만 아니라 스택,  재귀로도 구현을 할 수 있으니 구현해보시는 것도 연습이 될 수 있습니다.

아래는 위의 과정을 구현한 코드입니다.

 

코드

#include<iostream>
#include<queue>
#include<vector>

using namespace std;

int in_degree[11];     //진입차수
vector <int> adj[11];  //간선 연결정보


void Topological_Sort() {
	queue<int>q;
	for (int i = 1; i <= 6; i++)  
		if(in_degree[i] == 0)   //진입차수가 0인 꼭지점을 q에 넣음
			q.push(i); 

	while (!q.empty()) {    //진입차수가 0인 꼭지점이 없을때까지 반복
		int current = q.front();
		q.pop();
		cout << current << " ";  // 위상정렬된 꼭지점을 차례대로 출력
		for (int i = 0; i < adj[current].size(); i++) {
			int next = adj[current][i];
			in_degree[next] = in_degree[next] - 1;// 진입차수 1회 차감
			if (in_degree[next] == 0) // 진입차수 0인지 확인
				q.push(next); //진입차수가 0으로 바뀌면 다시 큐에 넣음
		}
	}
}


int main(void) {
	
    //연결정보, 진입차수 설정
	adj[1].push_back(2);
	in_degree[2]++;

	adj[2].push_back(3);
	in_degree[3]++;
	adj[4].push_back(3);
	in_degree[3]++;

	adj[3].push_back(6);
	in_degree[6]++;
	adj[5].push_back(6);
	in_degree[6]++;
	
	Topological_Sort();
}

위상정렬을 응용하여 다양한 문제들을 풀어 볼 수 있는 곳입니다.

위상정렬에 친숙해지는데 도움이 많이 되니 참고하시길 바랍니다.

https://www.acmicpc.net/problemset?sort=ac_desc&algo=78

문제 - 1 페이지