위상 정렬
📌위상 정렬순서가 정해져 있는 일련의 작업을 차례대로 수행해야 할 때 사용하는 알고리즘방향 그래프의 모든 노드를 방향성에 거스르지 않도록 순서대로 나열하는 것ex: 선수 과목을 고려한 학습 순서 설정 진입 차수: 특정한 노드로 들어오는 간선의 개수 1. 진입차수가 0인 노드를 큐에 넣는다.2. 큐가 빌때까지 다음 과정 반복한다. - 큐에서 원소를 꺼내 해당 노드에서 출발하는 간선을 그래프에서 제거한다. - 새롭게 진입차수가 0이 된 노드를 큐에 넣는다. 📌코드from collections import deque# 노드의 개수, 간선의 개수 입력v, e = map(int, input().split())# 모든 노드 진입차수 0으로 초기화indegree = [0] * (v + 1)# 각 노드에 연결된..
코딩테스트
2024. 11. 12. 19:47