[알고리즘 문제 풀기] 줄 세우기(2252)

1. 문제 풀이 아이디어

• 위상 정렬을 통해 순서가 정해진 작업들의 전체 순서를 구해 문제를 해결할 수 있다.

2. 나의 정답 코드

using System.Text;
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>();

    for (int i = 0; i < m; i++)
    {
        split = sr.ReadLine().Split();
        int a = int.Parse(split[0]);
        int b = int.Parse(split[1]);
        list[a].Add(b);
        count[b]++;
    }
    Queue<int> queue = new Queue<int>();
    for (int i = 1; i <= n; i++)
    {
        if (count[i] == 0) queue.Enqueue(i);
    }
    while (queue.Count > 0)
    {
        int cur = queue.Dequeue();
        sb.Append(cur).Append(' ');
        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(sb);
}

3. 정리

• list 배열에 각 정점에서 연결되는 정점들을 저장한다.

• count 배열에 각 정점으로 들어오는 간선의 개수를 저장한다.

• 진입 차수가 0인 정점을 큐에 넣고 하나씩 꺼내면서 결과에 추가한다.

• 꺼낸 정점과 연결된 다음 정점의 진입 차수를 줄이고, 0이 되면 큐에 넣는다.

• 모든 정점을 처리해 정렬된 결과를 출력하여 문제를 해결한다.