위상정렬

문제 링크:https://www.acmicpc.net/problem/1005 1005번: ACM Craft 첫째 줄에는 테스트케이스의 개수 T가 주어진다. 각 테스트 케이스는 다음과 같이 주어진다. 첫째 줄에 건물의 개수 N과 건물간의 건설순서 규칙의 총 개수 K이 주어진다. (건물의 번호는 1번부 www.acmicpc.net ▶문제 서기 2012년! 드디어 2년간 수많은 국민들을 기다리게 한 게임 ACM Craft (Association of Construction Manager Craft)가 발매되었다. 이 게임은 지금까지 나온 게임들과는 다르게 ACM크래프트는 다이나믹한 게임 진행을 위해 건물을 짓는 순서가 정해져 있지 않다. 즉, 첫 번째 게임과 두 번째 게임이 건물을 짓는 순서가 다를 수도 있다..

문제 링크: https://www.acmicpc.net/problem/2252 2252번: 줄 세우기 첫째 줄에 N(1 ≤ N ≤ 32,000), M(1 ≤ M ≤ 100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의 www.acmicpc.net 키를 정렬하는데 있어서 약간의 순서를 줬다. 즉 어떤 학생 앞에는 정해진 학생이 앞에 있어야 하는 것이다. arr배열에 조건의 수를 적어주고 list[해당 학생].add(앞에 서야하는 학생)식으로 선언해준다. arr[학생]==0 일 경우에 StringBuilder에 추가해주며 해당 학생 앞에 서야하는 학생의 arr을 낮춰준다. 이때 낮춰준 학..

문제 링크: https://www.acmicpc.net/problem/14567 14567번: 선수과목 (Prerequisite) 3개의 과목이 있고, 2번 과목을 이수하기 위해서는 1번 과목을 이수해야 하고, 3번 과목을 이수하기 위해서는 2번 과목을 이수해야 한다. www.acmicpc.net 원하는 과목을 듣기 위해선 선수 과목을 들어야 하는 문제이다. 즉 조건을 체크하면서 순서를 체크하는 문제이다. 순서대로 입력이 주어지므로 반복문을 통해서 첫 번째 강의부터 마지막 강의까지 조건들을 체크해주면 된다. 한 과목마다 조건의 최댓 값을 찾은 후 +1 해주면 해당 과목을 들을 수 있는 학기가 나온다. 과목마다 들을 수 있는 학기를 arr 배열에 담고 list[해당과목].add(조건)을 정리하여 찾으면 간..