다음 (가) 트리(tree)를 깊이 우선 탐색(DFS, Depth Fi… | [7급 국가직 알고리즘] 23년 1회차 기출문제 상세 페이지
1[7급 국가직 알고리즘] 23년 1회차
다음 (가) 트리(tree)를 깊이 우선 탐색(DFS, Depth First Search) 알고리즘으로 방문한 순서가 (나)와 같을 때, ㉠～㉢에 들어갈 노드는?(가)㉠ ㉡ ㉢
(나) a→b→c→d→e→f→g→h→i→j→k→l→m
1
e / g / c
2
e / h / i
3
k / g / i
4
k / h / c
해설
DFS 방문 순서를 트리에 대입하면 ㉠은 e, ㉡은 h, ㉢은 i이다.
깊이 우선 탐색의 방문 순서는 전위 순회 순서와 같다. a의 왼쪽 자식 b 아래에서 c와 그 자식 d, 둘째 자식 e(㉠), 셋째 자식 f와 그 자식 g·h(㉡)를 차례로 방문한다.
이어서 a의 오른쪽 자식 i(㉢)와 그 서브트리 j, k, l, m을 방문한다.
- e·g·c 조합: f의 두 자식 중 g가 먼저 방문되므로 ㉡ 자리는 h이고, c는 b의 첫 자식이다.
- k·g·i 조합: k는 a의 오른쪽 서브트리에 속해 b의 자식 자리에 올 수 없다.
- k·h·c 조합: ㉠은 b의 둘째 자식 e이고, ㉢은 오른쪽 서브트리의 루트 i이다.
오류나 개정된 내용이 보이면 알려주세요