방향그래프의 행(row)은 출발 노드로 열(column)은 도착 노드로… | [7급 국가직 자료구조론] 12년 1회차 기출문제 상세 페이지
1[7급 국가직 자료구조론] 12년 1회차
방향그래프의 행(row)은 출발 노드로 열(column)은 도착 노드로 매핑하여 다음과 같이 인접행렬로 표현될 때, 위상 정렬(topological sort)이 가능한 것은?
1
| a | b | c | d | e | f | |
|---|---|---|---|---|---|---|
| a | 1 | 1 | ||||
| b | 1 | 1 | ||||
| c | 1 | 1 | ||||
| d | 1 | 1 | ||||
| e | 1 | 1 | ||||
| f |
2
| a | b | c | d | e | f | |
|---|---|---|---|---|---|---|
| a | 1 | 1 | ||||
| b | 1 | 1 | ||||
| c | 1 | 1 | ||||
| d | 1 | |||||
| e | 1 | 1 | 1 | |||
| f |
3
| a | b | c | d | e | f | |
|---|---|---|---|---|---|---|
| a | 1 | 1 | ||||
| b | 1 | 1 | ||||
| c | 1 | 1 | ||||
| d | 1 | |||||
| e | 1 | 1 | ||||
| f |
4
| a | b | c | d | e | f | |
|---|---|---|---|---|---|---|
| a | 1 | 1 | ||||
| b | 1 | 1 | ||||
| c | 1 | 1 | ||||
| d | 1 | |||||
| e | 1 | 1 | ||||
| f | 1 |
해설
위상 정렬은 사이클이 없는 방향그래프(DAG)에서만 가능하므로, 사이클이 없는 인접행렬을 고르면 된다.
d에서 c로, e에서 b로, f에서 a로 되돌아가는 간선 없이 d→f, e→d, e→f 만 있는 행렬은 사이클이 없으며, a, b, c, e, d, f 순으로 위상 정렬된다.
- d→c 간선이 있는 행렬은 c→d와 함께 c→d→c 사이클이 생긴다.
- e→b 간선이 있는 행렬은 b→c→e→b 사이클이 생긴다.
- f→a 간선이 있는 행렬은 a→b→d→f→a 사이클이 생긴다.
오류나 개정된 내용이 보이면 알려주세요