[알고리즘 문제 풀기] 선수과목 (Prerequisite)(14567)

1. 문제 풀이 아이디어

• 각 노드마다 가장 긴 경로의 길이를 구해야 하므로, 역방향 그래프를 만든 후 DFS + 메모이제이션을 활용하여 해결한다.

2. 나의 정답 코드

using System.Text;
using System.Collections.Generic;

StringBuilder sb = new StringBuilder("");

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>();
    while (m > 0)
    {
        split = sr.ReadLine().Split();
        int a = int.Parse(split[0]);
        int b = int.Parse(split[1]);
        list[b].Add(a);
        m--;
    }
    for (int i = 1; i <= n; i++)
    {
        sb.Append(GetCount(i) + " ");
    }
    sw.WriteLine(sb);

    int GetCount(int num)
    {
        if (count[num] > 0)
            return count[num];
        if (list[num].Count == 0)
            return 1;
        int result = 0;
        foreach (int i in list[num]) result = Math.Max(result, GetCount(i) + 1);
        count[num] = result;
        return result;
    }
}

3. 정리

• list[b].Add(a);를 사용하여 역방향 그래프를 생성하여, 각 노드에서 시작했을 때의 최대 깊이를 계산한다.

• GetCount(num) 함수는 DFS와 메모이제이션을 활용하여 최장 경로 길이를 구한다.

• count[num]이 0보다 크다면 이미 방문한 노드이므로 즉시 반환하여 중복 계산을 방지한다.

• 모든 노드에 대해 GetCount(i)를 호출하여 결과를 출력한다.