선수과목처럼 노드 간의 선행조건들이 주어질 때 이를 모두 만족하는 순서대로 나열하거나 최소 소요시간 등을 구하는 알고리즘
- 노드 간의 관계가 주어질 때, 인접행렬로 관계 저장
ex) a 과목을 수강하기 위해서는 b, c 과목의 선수강이 필요하다고 하면 b[0]=a
, c[0]=a
처럼 b, c 다음에 갈 수 있는 노드로 a 를 저장
- 노드 간의 관계 주어질 때, 해당 노드의 선행 조건의 개수(차수)를 기록
➡️ 이는 모든 선행 조건을 만족했는지 확인하는 용도로 문제 조건에 따라서 생략하거나 다른 방법으로 대체 가능
ex) a 과목을 수강하기 위해서는 b, c 과목의 선수강이 필요하기 때문에 dgree[a]=2
형식으로 저장
- 선행 노드가 없는 노드는 큐에 저장하고 방문 처리
- 큐에 저장한 노드 순서대로 다음에 갈 수 있는 노드 탐색
1) 현재 노드에서 갈 수 있는 다음 노드가 이미 방문한 노드가 아니라면 다음 노드의 차수 차감
2) 다음 노드의 차수가 0이면 선행조건을 모두 만족한 것이므로 다음 노드를 큐에 저장하고 방문 처리
❗️ 방문 처리도 문제 조건에 따라 유동적이며 필수적인 것은 아님