위상 정렬 알고리즘 (그래프 이론 확장)

위상 정렬의 조건 주어진 그래프에서 위상 정렬을 하려면 1. 위상 정렬을 할 그래프는 간선이 방향성을 가지는 그래프여야 한다 2. 그래프 내부에 순환이 있으면 안된다 3. 위상 정렬에서는 여러 가지 답이 존재할 수 있따. 한 단계에서 큐에 새롭게 들어가는 원소가 2개 이상인 경우가 있다면 여러 가지 답이 존재한다 모든 원소를 방문하기 전에 큐가 빈다면 사이클이 존재한다고 판단할 수 있다. 스택을 활용한 DFS를 이용해 위상 정렬을 수행할 수도 있다. 주요 알고리즘 로직 연결된 선에 대한 정보(connection 배열)을 만들어주고 연결선의 갯수는 보통은 작은 쪽에 설정해준다(문제에 따라 유동적) 그리고 연결선은 queue를 pop시켜 리스트를 하나씩 뺼 떄마다 연결되어 있던 선들을 제거해주고 연결된 선이..

2021.04.04