그림과 같은 탐색 트리에서 시작 노드 A부터 깊이 우선 탐색(DFS)과… | [7급 국가직 인공지능] 24년 1회차 기출문제 상세 페이지
1[7급 국가직 인공지능] 24년 1회차
그림과 같은 탐색 트리에서 시작 노드 A부터 깊이 우선 탐색(DFS)과 너비 우선 탐색(BFS)을 수행할 경우 노드 F를 몇 번째로 방문하게 되는지를 각각 M과 N이라고 할 때, M + N의 값은? (단, 노드 A의 방문 순서는 1이고, 왼쪽 자식을 먼저 방문한다)
1
13
2
14
3
15
4
16
해설
노드 F의 방문 순서는 DFS에서 9, BFS에서 6이므로 M + N의 값은 15이다.
DFS는 왼쪽 자식부터 끝까지 내려간 뒤 되돌아오므로 A → B → D → G → E → H → I → C → F 순으로 방문해 F의 순서가 9가 된다.
BFS는 깊이별로 왼쪽부터 방문하므로 A → B → C → D → E → F 순이 되어 F의 순서가 6이 된다.
- 13: DFS에서 E의 자식 H, I를 세지 않아 F의 순서를 7로 잘못 센 합이다.
- 14: DFS에서 F를 8번째로 센 합으로, 실제 DFS 순서(9번째)와 다르다.
- 16: DFS나 BFS 중 한쪽 순서를 한 칸 더 센 값으로, 실제 방문 순서와 맞지 않는다.
오류나 개정된 내용이 보이면 알려주세요