[알고리즘 문제 풀기] 문제집(1766)

1. 문제 풀이 아이디어

• 위상 정렬을 적용하되, 진입 차수가 0인 정점을 우선순위 큐에 넣어 번호가 가장 작은 정점부터 처리해 문제를 해결할 수 있다.

2. 나의 정답 코드

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

class PriorityQueue<T>
{
	private List<Tuple<T, int>> _heap = new List<Tuple<T, int>>();
	private void Swap(int i, int j)
	{
		var temp = _heap[i];
		_heap[i] = _heap[j];
		_heap[j] = temp;
	}
	private void HeapifyUp(int index)
	{
		while (index > 0)
		{
			int parent = (index - 1) / 2;
			if (_heap[index].Item2 >= _heap[parent].Item2) break;
			Swap(index, parent);
			index = parent;
		}
	}
	private void HeapifyDown(int index)
	{
		int last = _heap.Count - 1;
		while (true)
		{
			int left = 2 * index + 1;
			int right = 2 * index + 2;
			int smallest = index;
			if (left <= last && _heap[left].Item2 < _heap[smallest].Item2)
				smallest = left;
			if (right <= last && _heap[right].Item2 < _heap[smallest].Item2)
				smallest = right;
			if (smallest == index) break;
			Swap(index, smallest);
			index = smallest;
		}
	}
	public void Enqueue(T item, int priority)
	{
		_heap.Add(Tuple.Create(item, priority));
		HeapifyUp(_heap.Count - 1);
	}
	public T Dequeue()
	{
		var root = _heap[0].Item1;
		_heap[0] = _heap[_heap.Count - 1];
		_heap.RemoveAt(_heap.Count - 1);
		HeapifyDown(0);
		return root;
	}
	public int PeekPriority()
	{
		return _heap[0].Item2;
	}
	public int Count => _heap.Count;
}

class Program
{
	static void Main(string[] args)
	{
		StringBuilder sb = new StringBuilder("");

		using (StreamReader sr = new StreamReader(Console.OpenStandardInput()))
			using (StreamWriter sw = new StreamWriter(Console.OpenStandardOutput()))
		{
			int[] input = Array.ConvertAll(sr.ReadLine().Split(), int.Parse);
			int n = input[0];
			int m = input[1];
			SortedSet<int>[] set = new SortedSet<int>[n + 1];
			for (int i = 1; i <= n; i++) set[i] = new SortedSet<int>();
			int[] p = new int[n + 1];
			for (int i = 0; i < m; i++)
			{
				input = Array.ConvertAll(sr.ReadLine().Split(), int.Parse);
				int a = input[0];
				int b = input[1];
				set[a].Add(b);
				p[b]++;
			}
			PriorityQueue<int> pq = new PriorityQueue<int>();

			for (int i = 1; i <= n; i++)
			{
				if (p[i] == 0) pq.Enqueue(i, i);
			}
			while (pq.Count > 0)
			{
				int cur = pq.Dequeue();
				sb.Append(cur + " ");
				foreach(int next in set[cur])
				{
					p[next]--;
					if (p[next] == 0) pq.Enqueue(next, next);
				}
			}
			sw.WriteLine(sb);
		}
	}
}

3. 정리

• set[a].Add(b)에서 인접 리스트를 구성하고, 동시에 p[b]++로 각 정점의 진입 차수를 기록한다.

• 진입 차수가 0인 정점을 모두 우선순위 큐에 넣는다. 이때 번호가 작을수록 우선순위가 높도록 동일한 값을 priority로 사용한다.

• 큐에서 하나씩 꺼내며 결과에 추가하고, 해당 정점에서 갈 수 있는 다음 정점들의 진입 차수를 1씩 줄인다.

• 새롭게 진입 차수가 0이 된 정점은 다시 큐에 넣는다.

• 모든 정점이 큐를 통해 빠지면, 위상 정렬된 결과가 나오고 이를 출력해 문제를 해결한다.