https://www.acmicpc.net/problem/14567 14567번: 선수과목 (Prerequisite) 3개의 과목이 있고, 2번 과목을 이수하기 위해서는 1번 과목을 이수해야 하고, 3번 과목을 이수하기 위해서는 2번 과목을 이수해야 한다. www.acmicpc.net 진입차수가 0 이면 queue에 넣어주고, queue에서 빼서 현재 노드 탐색하고, 현재 노드에서 인접한 노드들의 진입차수를 1씩 뺸다. 그리고 진입차수가 0이 되면 다시 queue에 넣어준다. 현재 최소 학기를 구해야 하므로 , queue에 enqueue하는게 몇번째인지 세어주는 count 도 같이 넣어준다. from collections import deque n, m = map(int, input().split()) ..
위상정렬
위상 정렬만 알면 날먹 가능한 문제이다 https://www.acmicpc.net/problem/2252 학생들을 줄 세워야 하는데 우선순위의 일부분이 m개 주어진다 이를 위상정렬 그래프로 생각하면 반드시 정점 a(학생1) 을 먼저 방문한 이후, 정점 b(학생2) 를 방문해야 한다 라는 순서가 된다. 위상정렬에서는 정점 b를 가기 위해서는 반드시 정점 a를 지나쳐야 하므로, 진입차수(indegree)가 1 증가하게 된다. # 위상 정렬 from collections import deque v, e = map(int, input().split()) indegree = [0]*(v+1) # 진입 차수 graph = [[] for _ in range(v+1)] for _ in range(e): a, b = m..
