위상 정렬 [1/1]

[ 위상 정렬이란? ]

• 순서가 정해져 있는 작업을 차례대로 수행
• 우선순위가 동일한 작업 사이에서는 순서가 상관 없음
• 무한 루프 구조가 되면 안됨 (두 작업이 서로의 선행 조건이 되는 경우)​

해당 작업 전에 할당된 작업이 있다면 그 작업들부터 끝내고 해당 작업을 진행한다는 의미입니다. "밥을 차린다 → 밥을 먹는다(반찬은 순서에 상관없이 먹는다) → 설거지를 한다(그릇은 순서에 상관없이 씻는다)" 의 과정과 같습니다. 순서에 상관 없는 과정도 있고, 꼭 순서가 필요한 과정도 있습니다. 이 중, 순서가 꼭 필요한 부분들을 정렬해주는 알고리즘이라고 볼 수 있습니다.

​

간단히 아래 그림과 같이, 4,2는 1이 수행된 이후에, 3은 4,2가 수행된 이후에 작업될 수 있습니다. 복잡한 그래프에서 이 순서를 파악하는 것이 위상 정렬이라고 할 수 있습니다.

 

 

---

 

왜 때문인지는 잘 모르겠지만 강의도 그렇고 인터넷에도 그렇고 순수 C언어로 작성된 코드는 안보이네요. 대부분 C++로 해결하는 것 같습니다. 하지만 전 C++은 할 줄 모르니 그냥 C로 작성해 보겠습니다. 일단 결과는 동일하게 도출됩니다.

​

위상정렬의 핵심 포인트는 "진입차순"을 두는 것입니다.

※ 진입차순 : 해당 작업의 직전에 수행해야 할 작업의 수
1의 진입차순 : 0
2의 진입차순 : 1
4의 진입차순 : 1
3의 진입차순 : 2
- 위 그래프 기준 위와 같이 볼 수 있습니다.

 

로직은 간단하게 진입차순이 0인 작업을 모두 수행하고, 그 뒤에 수행할 작업의 진입차수를 1개 줄여주는 방식입니다. 즉 아래와 같이 진행됩니다.

1 수행 : 2, 4의 진입차순 1 → 0
2 수행 : 3의 진입차순 2 → 1
4 수행 : 3의 진입차순 1 → 0
3 수행 : 수행완료

 

---

 

연결되는 데이터의 갯수가 일정하지 않으므로, 메인 배열을 제외한 나머지는 모두 연결리스트로 구성했습니다. 다들 C++로 짜서 C언어로는 모범답안이 없는지라.. 그냥 저 편한대로.. 계속 돌아가는 프로그램이 아니므로 동적할당을 따로 free해주지는 않았습니다.

 

 

 

 

 

※ 입력 예시
- 첫 줄은 노드가 아닌 노드범위 / 입력 회수 정보 (알고리즘 문제와 동일하게 함)
- 두 번째 줄 부터 첫 번재 노드 → 두 번째 노드를 의미

4 4
1 4
1 2
2 3
4 3

 

#include <stdio.h>
#include <stdlib.h>
#define SIZE 100  // 노드 최대 갯수

/* 해당 인덱스에 연결된 노드 */
typedef struct a link;
struct a {
	int num;  // 연결된 노드 이름(인덱스 번호)
	link* next;  // 다음 연결된 노드 주소
};

/* 해당 인덱스의 진입차수, 연결된 노드 */
typedef struct {
	int degree;  // 진입차수
	link* linked;  // 연결된 노드 정보
}data;

int topology_sort(data* arr[SIZE], int* result, int count);
void create_data(data* arr[SIZE], int index, int x);
void linking(data* arr[SIZE], int index, int x);
void print_all(data* arr[SIZE], int* result, int count);

int main()
{
	data* arr[SIZE] = { NULL };  // data 구조체 포인터 저장 배열
	int result[SIZE];  // 수행 결과 저장을 위한 스택

	/* data 입력 */
	int n, m;
	scanf_s("%d %d", &n, &m);  // 학생수, 비교 횟수 입력
	for (int i = 0; i < m; i++)
	{
		int index, x;  // 상위노드, 하위(연결)노드 임시저장
		scanf_s("%d %d", &index, &x);
		create_data(arr, index, x);			
	}
	
	/* 데이터 검증을 위한 count (전체 노드 수만큼 result에 값이 담겨야 함)*/
	int count = 0;
	for (int i = 0; i < SIZE; i++)
		if (arr[i] != NULL)
			count++;

	/* 위상 정렬 수행 */
	if (topology_sort(arr, result, count) == 1)
	{
		puts("정렬 실패, 데이터가 잘못되었습니다");
		return 1;
	}

	/* 전체 리스트 출력 */
	print_all(arr, result, count);
	return 0;
}

/* 위상정렬 수행 */
/* parameter : 데이터 저장 배열 arr, 결과 저장 result, 노드 갯수 */
/* return : 정상 == 0, 비정상 == 1 */
int topology_sort(data* arr[SIZE], int* result, int count)
{
	/* 정렬 수행을 위한 큐 */
	int queue[SIZE];	
	int n = 0;  // queue count
	int r = 0;  // result count
	
	/* 위상 정렬 수행 */
	while (1)
	{
		/* 진입차수가 0인 항목을 큐와 result에 동시에 담아줌 */
		for (int i = 0; i < SIZE; i++)
			if (arr[i] != NULL && arr[i]->degree == 0)
			{
				queue[n++] = i;
				result[r++] = i;
				arr[i]->degree--;
			}

		/* 종료 조건 */
		if (n == 0)
		{
			if (r == count)  // 전체 노드 갯수가 맞다면 정상 종료
				return 0;
			else return 1;
		}

		/* 큐에 담긴 노드에 연결된 노드의 degree 감소 */
		for (int i = 0; i < n; i++)
		{
			link* p = arr[queue[i]]->linked;
			while (p != NULL)
			{
				arr[p->num]->degree--;
				p = p->next;
			}
		}
		n = 0;	// queue count 초기화
	}
}

/* data 노드 만들기 */
/* parameter : 데이터 저장 배열 arr, index 노드에 연결된 노드 x */
/* return : void (메모리 할당 실패 시 프로그램 종료) */
void create_data(data* arr[SIZE], int index, int x)
{
	data* temp = NULL;
	if (arr[index] == NULL)  // 비어있을 경우 새로 생성
	{		
		if ((temp = (data*)malloc(sizeof(data))) == NULL)
			exit(1);
		temp->degree = 0;
		temp->linked = NULL;
		arr[index] = temp;
	}
	if (arr[x] == NULL)  // 비어있을 경우 새로 생성
	{
		if ((temp = (data*)malloc(sizeof(data))) == NULL)
			exit(2);
		temp->degree = 0;
		temp->linked = NULL;
		arr[x] = temp;
	}
	arr[x]->degree++;  // 진입차수 1 증가
	
	linking(arr, index, x);  // 연결된 노드 생성
}

/* 연결된 노드 -> data의 linked에 붙여주기 */
/* parameter : 데이터 저장 배열 arr, index 노드에 연결된 노드 x */
/* return : void (메모리 할당 실패 시 프로그램 종료) */
void linking(data* arr[SIZE], int index, int x)
{
	link* temp = NULL;
	if ((temp = (link*)malloc(sizeof(link))) == NULL)
		exit(3);
	temp->num = x;  // 연결된 노드 
	temp->next = NULL;  // 다음 연결 노드 (기본값 NULL)

	if (arr[index]->linked == NULL)  // 현재 연결 노드가 하나도 없을 때
		arr[index]->linked = temp;
	else  // 현재 연결 노드가 있을 때
	{
		link* p = arr[index]->linked;
		while (p->next != NULL)
			p = p->next;
		p->next = temp;  // 마지막 연결 노드에 붙여줌
	}
}


/* 전체 리스트 출력 */
/* parameter : data 배열 arr, 노드 갯수 count */
/* return : void */
void print_all(data* arr[SIZE], int* result, int count)
{
	printf("\n");
	for (int i = 0; i < SIZE; i++)
		if (arr[i] != NULL)
		{
			printf("  num : %d ", i);
			link* p = arr[i]->linked;
			if (p != NULL) printf("->");
			while (p != NULL)
			{
				printf(" %d ", p->num);
				p = p->next;
			}
			printf(" (degree : %d)\n", arr[i]->degree);
		}
	printf("\n  최종결과 : ");
	for (int i = 0; i < count; i++)
		printf("%d ", result[i]);
	printf("\n");
}