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 풀이 과정 입력값은 키를 비교한 학생 A와 B의 순서가 M개만큼 주어진다. 바로 이전에 풀었던 ACMCraft와 비슷한 유형인 거 같아 같은 방법으로 해결했다. 위상 정렬만 알면 간단하게 해결 가능하다. from collections import deque import sys input = sys.stdin.readline N, M = map(int,in..
https://www.acmicpc.net/problem/1005 1005번: ACM Craft 첫째 줄에는 테스트케이스의 개수 T가 주어진다. 각 테스트 케이스는 다음과 같이 주어진다. 첫째 줄에 건물의 개수 N과 건물간의 건설순서 규칙의 총 개수 K이 주어진다. (건물의 번호는 1번부 www.acmicpc.net 풀이 과정 처음에 for 문을 사용해서 풀었다. 예제 기준으로 1 2 3 4처럼 순서대로인 경우는 정답이 맞지만. 3 -> 2 -> 1과 같이 순서가 거꾸로인 경우 답이 틀리게 나온다. 순서를 내가 원하는 대로 정하면 해결이 될 거 같아 방법을 찾아보던 도중 위상 정렬이라는 것을 알았다. 큐를 사용해서 진입 차수가 0인 것들을 그래프에서 pop해주며 정렬해주면 된다. 위 그림을 보면 node..