위상정렬 (topological sorting)

참고: https://gmlwjd9405.github.io/2018/08/27/algorithm-topological-sort.html

[알고리즘] 위상 정렬(Topological Sort)이란 - Heee's Development Blog

위상 정렬(Topological Sort)을 이용한 기본적인 해결 방법

 

위상정렬 순서

1. 진입 차수가 0인 정점(즉, 들어오는 간선의 수가 0)을 선택
진입 차수가 0인 정점이 여러 개 존재할 경우 어느 정점을 선택해도 무방하다.
초기에 간선의 수가 0인 모든 정점을 큐에 삽입

2. 선택된 정점과 여기에 부속된 모든 간선을 삭제
선택된 정점을 큐에서 삭제
선택된 정점에 부속된 모든 간선에 대해 간선의 수를 감소

3. 위의 과정을 반복해서 모든 정점이 선택, 삭제되면 알고리즘 종료

 

위상정렬 예제

백준 2252:줄 세우기 https://www.acmicpc.net/problem/2252

2252번: 줄 세우기

 

소스코드

 

 

백준 1516: 게임 개발https://www.acmicpc.net/problem/1516

1516번: 게임 개발

 

핵심: 해당 노드로 가는데 드는 비용은 계속해서 갱신(최댓값으로, 왜냐하면 최소한 그 시간이 지나야 새로운 건물을 지을 수 있기 때문 )하다가 q에 push하는 과정은  진입차수(degree)가 0이 될 때 push하면 된다.

 

소스코드