<보기>와 같은 간선(edge)을 갖는 방향 그래프에 대하여… | [7급 서울시 알고리즘] 26년 1회차 기출문제 상세 페이지
1[7급 서울시 알고리즘] 26년 1회차
<보기>와 같은 간선(edge)을 갖는 방향 그래프에 대하여 가능한 위상 정렬(topological sort) 결과의 개수로 가장 옳은 것은? (단, 정점은 A, B, C, D, E 5개이다.)<보기>
A→B A→C B→E C→E D→E
1
4
2
6
3
8
4
12
해설
가능한 위상 정렬은 8가지다.
E는 B, C, D 모두의 뒤에 와야 하고 A는 B, C보다 앞서야 하므로, E는 항상 마지막이다.
A, B, C는 A 다음에 B, C가 어느 순서로든 올 수 있어 2가지이고, 제약이 없는 D를 네 자리 중 하나에 끼워 넣으면 된다.
- 4가지: B와 C의 순서를 하나로 고정하고 센 값이다.
오류나 개정된 내용이 보이면 알려주세요