다음 조건에 따라 주어진 그래프에 대해 깊이 우선 탐색(DFS, Dep… | [7급 국가직 알고리즘] 25년 1회차 기출문제 상세 페이지
1[7급 국가직 알고리즘] 25년 1회차
다음 조건에 따라 주어진 그래프에 대해 깊이 우선 탐색(DFS, Depth First Search) 방법을 이용하여 트리를 만들 경우, 나올 수 있는 트리의 개수와 수행하는 백트래킹 횟수를 바르게 연결한 것은?○ DFS의 시작 정점은 A로 하고, 정점의 접근 순서는 알파벳 순서로 한다.
○ DFS는 사이클을 형성하지 않으면서 백트래킹을 통해 시작 정점으로 돌아왔을 때, 시작 정점에서 방문하지 않은 접근 가능한 인접 정점이 없으면 종료한다.
○ DFS의 종료시점에 그래프에 방문하지 않은 정점들이 존재하면, 방문하지 않은 정점들 중 알파벳 순서가 가장 앞선 정점을 시작 정점으로 하여 DFS를 다시 시작한다.
○ 그래프 안에 방문하지 않은 정점이 존재하지 않을 때까지 DFS를 반복한다.
1
트리의 개수 1 / 백트래킹 횟수 3
2
트리의 개수 1 / 백트래킹 횟수 4
3
트리의 개수 2 / 백트래킹 횟수 3
4
트리의 개수 2 / 백트래킹 횟수 5
해설
DFS를 조건대로 수행하면 트리는 2개, 백트래킹은 5회이다.
A에서 시작해 A → B → C로 내려가면 C는 나가는 간선이 없어 B로 되돌아가고(1회), B → D로 간 뒤 D의 인접 정점 A·C가 모두 방문되어 B로(2회), B에서 더 갈 곳이 없어 A로(3회) 되돌아간다.
A → F로 간 뒤 F의 인접 정점 A·C가 이미 방문되어 A로 되돌아가고(4회), A에 남은 정점이 없어 첫 트리 {A, B, C, D, F}가 끝난다.
남은 정점 중 가장 앞선 E에서 다시 시작해 E → G로 간 뒤 G의 인접 정점 D·E가 방문되어 E로 되돌아가며(5회), 두 번째 트리 {E, G}가 만들어진다.
- 트리 1개·백트래킹 3회 조합: E와 G는 A에서 출발하는 간선으로 도달할 수 없어 DFS를 다시 시작해야 하므로 트리가 2개이다.
- 트리 1개·백트래킹 4회 조합: 4회는 첫 트리의 백트래킹만 센 값이며, E에서 다시 시작하는 두 번째 트리가 빠졌다.
- 트리 2개·백트래킹 3회 조합: 첫 트리에서만 4회, 두 번째 트리에서 1회가 발생해 합계 5회이다.
오류나 개정된 내용이 보이면 알려주세요