목록위상정렬 (2)
while (1): study();
출처: https://www.acmicpc.net/problem/3665 3665번: 최종 순위 올해 ACM-ICPC 대전 인터넷 예선에는 총 n개의 팀이 참가했다. 팀은 1번부터 n번까지 번호가 매겨져 있다. 놀랍게도 올해 참가하는 팀은 작년에 참가했던 팀과 동일하다. 올해는 인터넷 예선 본부에 www.acmicpc.net 아이디어를 떠올리는 것에 상당히 애를 먹었던 문제일뿐만 아니라, 예외사항에 대해서 모두 고려해야 했던 쉽지 않았던 문제입니다. 다만 후술하겠지만 아이디어를 떠올린 이후에는 구현이 그다지 어렵지 않고, 채점 케이스도 허술하기 때문에.. 어려우면서도 쉬운(?) 문제였던 것 같습니다. 풀이 위상정렬 알고리즘을 사용하는 대표적인 문제로 '선수과목 문제'를 떠올려볼 수 있습니다. 이 문제는 ..
위상 정렬 알고리즘은 방향 그래프의 모든 노드들을 방향성에 거스르지 않도록 순서대로 나열하는 정렬 기법을 의미합니다. 기존의 서로소 집합 알고리즘이나, 이를 기반으로 한 크루스칼 알고리즘은 무향 그래프에 대해서 동작했던 것을 생각하면 차이가 있습니다. 예를 들어 '선수과목을 고려한 학습 순서 설정 문제' 등에서 대표적으로 사용될 수 있습니다. 1. 각 노드의 진입차수(indegree)를 저장합니다. 2. 진입차수가 0인 노드부터 시작하여 연결된 노드에 대해 진입차수를 1씩 뺍니다. 3. 다른 노드도 진입차수가 0이 될 경우 2의 동작을 반복합니다. 큐를 사용하여 구현할 경우 위상정렬의 시간복잡도는 O(V+E)입니다. 전체 소스코드는 다음과 같습니다. input1 = '''7 8 1 2 1 5 2 3 2 ..