코테 스터디 39일차 TIL + 오늘의 학습 키워드 위상정렬2 이게더 쉬움

- 오늘의 학습 키워드 위상정렬2

- 공부한 내용 본인의 언어로 정리하기

그래프 모델링 선수과목 관계를 방향 그래프로 표현

사이클 검출: DFS 또는 위상 정렬 사용하여 사이클 존재 여부 확

사이클 없으면 모든 과목 수강 가능. 있으면 불가능

 

1. 선수과목 관계를 방향 그래프로 모델링

2. 각 과목이 가져야할 선수과목 개수 계산

3. 선수과목이 없는 과목부터 차례로 수강

4. 과목을 수강할때마다 그 과목을 선수 과목으로 하는 다른 과목들의 진입 차수 감소

5. 모든 과목을 수강할수 있으면 true. 사이클 때문에 불가능하면 false

 

수도 코드

1. 그래프 인접 리스트 생성
2. 각 노드의 진입차수 (indegree) 계산
3. 진입 차수가 0인 노드들을 큐에 추가
4. 큐가 빌 때 까지:
  -큐에서 노드 하나 제거
  - 처리된 노드 개수 증가
  -해당 노드의 모든 인접 노드의 진입차수 감소
  -진입 차수가 0이 된 노드를 큐에 추가
 5. 처리된 노드 개수가 전체 과목 수와 같으면 true. 아니면 false

 

- 오늘의 회고
  - 어떤 문제가 있었고, 나는 어떤 시도를 했는지
  - 어떻게 해결했는지
  - 무엇을 새롭게 알았는지
  - 내일 학습할 것은 무엇인지