[7급 국가직 알고리즘 2025년 18번]

다음 조건에 따라 주어진 그래프에 대해 깊이 우선 탐색(DFS, Depth First Search) 방법을 이용하여 트리를 만들 경우, 나올 수 있는 트리의 개수와 수행하는 백트래킹 횟수를 바르게 연결한 것은?

○ DFS의 시작 정점은 A로 하고, 정점의 접근 순서는 알파벳 순서로 한다.

○ DFS는 사이클을 형성하지 않으면서 백트래킹을 통해 시작 정점으로 돌아왔을 때, 시작 정점에서 방문하지 않은 접근 가능한 인접 정점이 없으면 종료한다.

○ DFS의 종료시점에 그래프에 방문하지 않은 정점들이 존재하면, 방문하지 않은 정점들 중 알파벳 순서가 가장 앞선 정점을 시작 정점으로 하여 DFS를 다시 시작한다.

○ 그래프 안에 방문하지 않은 정점이 존재하지 않을 때까지 DFS를 반복한다.

트리의 개수 백트래킹 횟수