[알고리즘 문제 풀기]

1. 문제 풀이 아이디어

• 각 가수의 순서를 그래프의 간선 관계로 표현하고, 진입 차수를 기반으로 위상 정렬을 활용하여 문제를 해결할 수 있다.

2. 나의 정답 코드

using (StreamReader sr = new StreamReader(Console.OpenStandardInput()))
    using (StreamWriter sw = new StreamWriter(Console.OpenStandardOutput()))
{
    string[] split = sr.ReadLine().Split();
    int n = int.Parse(split[0]);
    int m = int.Parse(split[1]);
    List<int>[] list = new List<int>[n + 1];
    int[] count = new int[n + 1];
    for (int i = 1; i <= n; i++) list[i] = new List<int>();

    for (int i = 0; i < m; i++)
    {
        int[] nums = Array.ConvertAll(sr.ReadLine().Split(), int.Parse);
        for (int j = 1; j < nums.Length - 1; j++)
        {
            list[nums[j]].Add(nums[j + 1]);
            count[nums[j + 1]]++;
        }
    }
    Queue<int> queue = new Queue<int>();
    List<int> result = new List<int>();
    for (int i = 1; i <= n; i++)
    {
        if (count[i] == 0) queue.Enqueue(i);
    }
    while (queue.Count > 0)
    {
        int cur = queue.Dequeue();
        result.Add(cur);
        for (int i = 0; i < list[cur].Count; i++)
        {
            int next = list[cur][i];
            count[next]--;
            if (count[next] == 0) queue.Enqueue(next);
        }
    }
    sw.WriteLine(result.Count == n ? string.Join("\n", result) : "0");
}

3. 정리

• list[a]에 b를 추가하고, count[b]를 증가시켜 간선 관계를 저장한다.

• count[i] == 0인 모든 i를 queue에 넣어 시작점을 정한다.

• 큐에서 cur를 꺼내 result에 추가하고, list[cur]에 연결된 next들의 count[next]를 감소시킨다.

• count[next] == 0이면 다시 queue에 넣어 위상 정렬을 진행한다.

• 정렬된 result의 길이가 n이면 순서를 출력하고, 그렇지 않으면 "0"을 출력한다.