C# 코딩테스트 강좌, 위상 정렬

1. 위상 정렬이란?

위상 정렬은 방향 그래프에서 노드들을 선형으로 정렬하는 방법입니다. 이 정렬의 가장 큰 특징은 그래프 내의 모든 간선들이
정렬된 노드의 순서를 따르는 것입니다. 즉, 만약 노드 A에서 노드 B로 향하는 간선이 있다면, 노드 A는 노드 B보다 선행해야
합니다. 이러한 성질을 갖는 위상 정렬은 주로 작업의 순서를 정하거나, 스케줄링 문제에서 많이 사용됩니다.

위상 정렬은 Directed Acyclic Graph(Directed Acyclic Graph, DAG)에서만 적용할 수 있습니다.
사이클이 존재하는 경우, 위상 정렬을 할 수 없으며, 이는 그래프의 특성상 불가능한 상태를 의미합니다.
위상 정렬을 구현하는 방법에는 크게 2가지가 있습니다.
1) DFS(Depth First Search) 기반 방법
2) Kahn의 알고리즘

2. 문제 설명

다음은 위상 정렬을 이용해야 하는 문제입니다.

문제: 과목 이수 순서

당신은 대학생입니다. 여러 과목을 이수해야 졸업할 수 있습니다. 각 과목의 이수 조건은 다른 과목을 먼저
이수해야 한다는 것입니다. 이 정보를 바탕으로 각 과목의 이수 순서를 출력하세요. 만약 이수 순서가
불가능한 경우 “IMPOSSIBLE”이라고 출력해야 합니다.

입력 형식:
– 첫 번째 줄에는 과목의 수 N(1 ≤ N ≤ 1000)과 선행 과목의 수 M(0 ≤ M ≤ 100,000)이 주어진다.
– 그 다음 M줄에는 선행 과목 관계를 나타내는 두 개의 정수가 u, v가 주어진다. 이 경우 과목 u를 먼저 이수한 후
과목 v를 이수해야 한다.

출력 형식:
– 각 과목의 이수 순서를 한 줄에 하나씩 출력한다.
– 만약 이수 순서가 불가능한 경우 “IMPOSSIBLE”이라고 출력한다.

3. 문제 해결 과정

먼저, 입력을 통해 각 과목의 수와 선행 과목의 관계를 파악해야 합니다. 이를 위해 인접 리스트를 사용하여
그래프를 표현합니다. 그리고 각 노드의 차수를 저장하기 위한 배열을 하나 만들어야 합니다.
차수는 해당 노드의 선행 과목의 개수를 나타냅니다.

1) 그래프 구축:
– 입력으로 주어진 선행 과목 관계를 바탕으로 인접 리스트와 차수 배열을 구축합니다.

2) 차수를 활용한 위상 정렬:
– 차수가 0인 노드를 큐에 추가합니다. 이 경우 해당 과목은 선행 과목이 없으므로 먼저 이수할 수 있습니다.
– 큐에서 노드를 꺼내고, 이와 연결된 노드들의 차수를 1 감소시킵니다. 만약 차수가 0이 된다면, 해당 노드를 큐에 추가합니다.
– 이 과정을 반복하여 모든 노드를 처리합니다. 만약 처리된 노드의 수가 총 과목 수와 같지 않다면, 사이클이 존재하는 것이므로 “IMPOSSIBLE”을 출력해야 합니다.

4. C# 코드 구현

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        // 입력 받기
        int N = int.Parse(Console.ReadLine());
        int M = int.Parse(Console.ReadLine());

        // 인접 리스트와 차수 배열 초기화
        List[] graph = new List[N + 1];
        int[] inDegree = new int[N + 1];

        for (int i = 1; i <= N; i++)
        {
            graph[i] = new List();
        }

        // 선행 과목 관계 입력받기
        for (int i = 0; i < M; i++)
        {
            string[] input = Console.ReadLine().Split();
            int u = int.Parse(input[0]);
            int v = int.Parse(input[1]);

            graph[u].Add(v);
            inDegree[v]++;
        }

        // 큐와 결과 리스트 초기화
        Queue queue = new Queue();
        List result = new List();

        // 차수가 0인 노드 큐에 추가
        for (int i = 1; i <= N; i++)
        {
            if (inDegree[i] == 0)
            {
                queue.Enqueue(i);
            }
        }

        // 위상 정렬
        while (queue.Count > 0)
        {
            int node = queue.Dequeue();
            result.Add(node);

            foreach (int neighbor in graph[node])
            {
                inDegree[neighbor]--;
                if (inDegree[neighbor] == 0)
                {
                    queue.Enqueue(neighbor);
                }
            }
        }

        // 결과 출력
        if (result.Count != N)
        {
            Console.WriteLine("IMPOSSIBLE");
        }
        else
        {
            foreach (int course in result)
            {
                Console.WriteLine(course);
            }
        }
    }
}

        

이 코드는 주어진 과목 수와 선행 과목 관계를 바탕으로 위상 정렬을 수행하는 방법을 보여줍니다.
그래프의 간 선행 관계에 따라 각 과목을 선형으로 정렬할 수 있습니다.

5. 결론

위상 정렬은 그래프 이론에서 매우 중요한 알고리즘 중 하나입니다.
실질적으로 많은 문제에서 적용이 가능하여, 프로그래밍 테스트에서도 자주 출제되는 주제입니다.
위 문제를 통해 위상 정렬을 어떻게 활용할 수 있는지를 이해하는 데 도움이 되었길 바랍니다.

이제 여러분은 C#을 사용하여 위상 정렬을 구현하고, 다양한 문제에 적응할 수 있는 기술을 갖추게 되었습니다.
앞으로도 위상 정렬을 필요로 하는 다양한 문제에 도전해 보시길 바랍니다.