위상정렬 2

[Graph] 백준-2252 줄 세우기 골드3 (Python)

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 풀의 진입 차수를 담아줄 리스트를 초기화한다. 진출 정보를 담아줄 리스트를 초기화한다. 진입 차수가 0인 것들을 큐에 담아준다. 큐에 값을 꺼내면서 결과 리스트에 큐의 값을 넣어준다. 해당 큐의 값에 진출 정보를 담는 리스트에서 진출 정보를 꺼내면서 해당 진출 정보와 관련된 진입 차수를 줄여준다. 진입 차수가 0이라면 큐에 담아준다. 코드 (Python)..

Algorithm 2023.05.25

[Graph] 백준-14567 선수과목(Prerequisite) 골드5 (Python)

https://www.acmicpc.net/problem/14567 14567번: 선수과목 (Prerequisite) 3개의 과목이 있고, 2번 과목을 이수하기 위해서는 1번 과목을 이수해야 하고, 3번 과목을 이수하기 위해서는 2번 과목을 이수해야 한다. www.acmicpc.net 진입 차수 : 특정한 노드로 들어오는 간선의 개수 진출 차수 : 특정한 노드에서 나가는 간선의 개수 풀의 진입 차수를 담아줄 리스트를 초기화한다. 진출 정보를 담아줄 리스트를 초기화한다. 진입 차수가 0인 것들을 큐에 담아준다. 큐에 값을 꺼내면서 해당 큐의 값에 진출 정보를 담는 리스트에서 진출 정보를 꺼내면서 해당 진출 정보와 관련된 진입 차수를 줄여준다. 큐의 값 이후에 진행되야 하므로 해당값의 결과보다 1보다 작다면..

Algorithm 2023.05.23