[크래프톤 정글] 위상 정렬

참고 자료 - https://m.blog.naver.com/ndb796/221236874984

1. 위상정렬 (Topological Sorting)

위상정렬은 그래프 이론에서 나오는 개념으로, 순서를 정하는 문제에서 사용된다. 특히, 방향성이 있는 비순환 그래프(Directed Acyclic Graph, DAG)에서 각 노드를 선행 관계에 맞춰 순서대로 나열하는 것을 의미한다.

대표적인 예시를 하나 들자면

위의 사진에서 보다 시피 우리가 졸업을 하기 위해서는 필요한 조건들이 존재하고 그 조건들에 순서가 존재 할때 그 순서를 결정 해주는 알고리즘이라 할 수 있다.

스택을 이용한 방식과 큐를 이용한 방식이 있는 데 큐를 이용하는 방법이 더 많이 사용되고 , 고급 알고리즘이라 큐를 이용한 방법을 정리 해보고자 한다.

위의 작업들을 그래프로 표현 하면 다음과 같다.

위와같이 들어갈수 있따.

여기서 각 노드 들의 진입 차수를 결정하면

이와같이 결정 할 수 있다 .

즉 이 상태에서 위상정렬 을 실행 하면 순서는 다음과 같다.

1. 모든 작업의 진입 차수를 계산한다. (즉, 각 작업이 다른 작업에 얼마나 의존하는지 파악한다.)
2. 진입 차수가 0인 작업들을 먼저 찾는다. 이 작업들은 선행 작업 없이 바로 할 수 있는 작업들이다.
3. 진입 차수가 0인 작업들을 큐에 넣고 하나씩 꺼내서 순서대로 처리한다.
4. 작업을 처리할 때마다 그 작업이 끝났으니, 그 작업과 연결된 다른 작업의 진입 차수를 1씩 줄인다.
5. 진입 차수가 0이 된 작업이 새로 생기면, 그 작업도 큐에 넣는다.
6. 큐가 빌 때까지 이 과정을 반복하면서 순서대로 작업을 처리한다.

이렇게 하면, 진입 차수가 0인 작업부터 시작해서 선행 작업을 마친 후에야 다음 작업을 할 수 있는 순서대로 모든 작업을 완료할 수 있다.

위상정렬 구현 (Kahn's Algorithm, Clang)

#include <stdio.h>
#include <stdlib.h>

#define MAX 100  // 최대 노드 수

// 인접 리스트를 표현할 구조체
typedef struct Node {
    int vertex;
    struct Node* next;
} Node;

Node* graph[MAX];  // 인접 리스트 그래프
int inDegree[MAX]; // 각 노드의 진입 차수를 저장하는 배열
int queue[MAX];    // 큐 배열
int front = -1, rear = -1; // 큐의 front와 rear 포인터

// 큐에 노드를 삽입하는 함수
void enqueue(int vertex) {
    if (rear == MAX - 1) {
        printf("큐가 가득 찼습니다!\n");
        return;
    }
    if (front == -1) {
        front = 0;
    }
    queue[++rear] = vertex;
}

// 큐에서 노드를 꺼내는 함수
int dequeue() {
    if (front == -1 || front > rear) {
        printf("큐가 비어 있습니다!\n");
        return -1;
    }
    return queue[front++];
}

// 그래프의 간선을 추가하는 함수
void addEdge(int start, int end) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->vertex = end;
    newNode->next = graph[start];
    graph[start] = newNode;
}

// 위상 정렬 함수 (Kahn's Algorithm)
void topologicalSort(int n) {
    int result[MAX];  // 위상 정렬 결과를 저장할 배열
    int count = 0;    // 처리된 노드의 개수

    // 진입 차수가 0인 노드를 큐에 삽입
    for (int i = 0; i < n; i++) {
        if (inDegree[i] == 0) {
            enqueue(i);
        }
    }

    // 큐가 빌 때까지 반복
    while (front <= rear) {
        int current = dequeue();  // 큐에서 노드를 꺼냄
        result[count++] = current;  // 결과 배열에 추가

        // 현재 노드와 연결된 노드들의 진입 차수를 1 감소
        Node* temp = graph[current];
        while (temp != NULL) {
            inDegree[temp->vertex]--;
            if (inDegree[temp->vertex] == 0) {
                enqueue(temp->vertex);
            }
            temp = temp->next;
        }
    }

    // 위상 정렬이 성공적으로 완료되지 못한 경우 (사이클 존재)
    if (count != n) {
        printf("사이클이 존재하여 위상 정렬을 수행할 수 없습니다.\n");
        return;
    }

    // 위상 정렬 결과 출력
    printf("위상 정렬 결과: ");
    for (int i = 0; i < count; i++) {
        printf("%d ", result[i]);
    }
    printf("\n");
}

int main() {
    int n, e;
    printf("노드의 개수와 간선의 개수를 입력하세요: ");
    scanf("%d %d", &n, &e);

    // 그래프 초기화 및 진입 차수 배열 초기화
    for (int i = 0; i < n; i++) {
        graph[i] = NULL;
        inDegree[i] = 0;
    }

    // 간선 정보 입력
    printf("간선 정보를 입력하세요 (시작 정점 끝 정점): \n");
    for (int i = 0; i < e; i++) {
        int u, v;
        scanf("%d %d", &u, &v);
        addEdge(u, v);
        inDegree[v]++;  // 끝 정점의 진입 차수 증가
    }

    // 위상 정렬 수행
    topologicalSort(n);

    return 0;
}

코드 설명:

1. graph: 각 노드가 가진 간선 정보를 인접 리스트로 표현했다. graph[i]는 노드 i가 가리키는 노드들의 리스트를 나타낸다.
2. inDegree: 각 노드의 진입 차수를 저장하는 배열이다. 진입 차수가 0인 노드들부터 차례로 처리된다.
3. queue: 진입 차수가 0인 노드들을 처리하기 위한 큐를 배열로 구현했다.
4. enqueue, dequeue: 큐에 노드를 삽입하고, 꺼내는 함수이다.
5. addEdge: 그래프에 간선을 추가하는 함수이다. 시작 노드에서 끝 노드로 가는 간선을 인접 리스트에 추가하며, 끝 노드의 진입 차수를 1 증가시킨다.
6. topologicalSort: Kahn's Algorithm을 이용하여 위상 정렬을 수행하는 함수이다.
   • 처음에 진입 차수가 0인 노드들을 큐에 삽입한다.
   • 큐에서 하나씩 노드를 꺼내면서, 그 노드에 연결된 다른 노드들의 진입 차수를 감소시킨다.
   • 진입 차수가 0이 된 노드를 큐에 추가하고, 큐가 빌 때까지 이 과정을 반복한다.
7. 사이클 검출: 처리된 노드의 개수가 전체 노드의 개수와 다르면, 이는 사이클이 존재하는 그래프임을 의미한다.

입출력 예시:

입력:

노드의 개수와 간선의 개수를 입력하세요: 6 6
간선 정보를 입력하세요 (시작 정점 끝 정점):
5 2
5 0
4 0
4 1
2 3
3 1

출력:

위상 정렬 결과: 4 5 2 3 1 0

이 예시에서는 노드 4, 5가 먼저 처리되고, 그 후에 다른 노드들이 의존성에 맞춰 처리되며, 위상 정렬 결과가 도출된다.

코드의 시간 복잡도:

• 이 알고리즘의 시간 복잡도는 O(V + E)이다. 여기서 V는 노드의 개수, E는 간선의 개수이다.