미새문지

위상정렬 알고리즘 줄 세우기 문제를 풀기 위해 학습했던 알고리즘 from collections import deque # 위상정렬 알고리즘(꼭짓점, 간선정보 매개체) def topological_sort(vertices, edges): # 각 꼭짓점에서 다른 꼭짓점으로의 간선정보를 저장할 인접리스트 만들기 # 함수를 사용할 때마다 새롭게 작성해야하므로 함수 내부에 작성 # 0은 무시하고 1부터시작해야하기 때문에 +1로 맞춤 adj = [[] for _ in range(vertices + 1)] # 꼭짓점으로 들어오는 간선의 수를 저장할 리스트 # 0은 무시하고 1부터시작해야하기 때문에 +1로 맞춤 indegree = [0] * (vertices + 1) # 간선 정보를 돌리면서 for edge in ed..

위상정렬 수서가 정해져 있는 작업을 차례로 수행해야 할 때 그 순서를 결정해 주기 위해 사용하는 알고리즘 답이 한 가지가 아니라 여러 가지가 존재할 수 있고 DAG(Directed Acyclic Graph)에만 적용이 가능하다. DAG는 사이클이 발생하지 않는 방향 그래프이며, 사이클이 발생하면 위상정렬을 수행할 수 없다. 위상정렬은 두 가지 해결책을 낼 수 있는데 현재 그래프가 위상정렬이 가능한지, 위상정렬이 가능하면 그 결과는 무엇인지이고 스택과 큐를 이용해 알고리즘을 짤 수 있다. 진행 과정(큐를 사용) 1. 진입차수가 0인 정점을 큐에 삽입 2. 큐에서 원소를 꺼내 연결된 모든 간선 제거 3. 간선 제거 이후 진입차수가 0이 된 정점을 큐에 삽입 4. 큐가 빌 때 까지 2번, 3번 과정 반복. 모..