<보기>와 같은 간선(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를 네 자리 중 하나에 끼워 넣으면 된다.
2×4=82\times 4=8

  • 4가지: B와 C의 순서를 하나로 고정하고 센 값이다.

오류나 개정된 내용이 보이면 알려주세요

이어서 풀어보기

[7급 서울시 알고리즘] 26년 1회차 20문항 이어서 보기문제·정답·해설을 한 페이지에서 이어서 볼 수 있어요7급 서울시 알고리즘 기출문제 암기장 전체 보기