2021년 3회 정보처리기사 기출문제 23번

23. 다음 그래프에서 정점 A를 선택하여 깊이우선탐색(DFS)으로 운행한 결과는?

 ① ABECDFG     ② ABECFDG

 ③ ABCDEFG     ❹ ABEFGCD

 

<해설>

DFS 탐색 방법

1. 시작 노드(A)에서 시작합니다.
2. 방문한 노드는 다시 방문하지 않으며, 연결된 노드 중 방문하지 않은 노드가 있으면 그 노드로 이동합니다.
3. 더 이상 이동할 수 없는 경우, 직전 노드로 돌아가서 다른 경로를 탐색합니다.

DFS 탐색 과정

1. A 방문 → B 선택
2. B 방문 → E 선택
3. E 방문 → F 선택
4. F 방문 → G 선택
5. G 방문 (더 이상 갈 곳 없음, 되돌아감)
6. F에서 다른 노드 확인 (C로 이동)
7. C 방문 → D 선택
8. D 방문 (끝)

DFS 방문 순서

A → B → E → F → G → C → D

정답

정답은 ④ ABEFGCD 입니다.