2019년 2회 정보처리기사 기출문제 9번

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

   ① ABECDFG     ② ABECFDG

   ③ ABCDEFG     ❹ ABEFGCD

 

 

 

 

---

🧠 문제 요약

다음 그래프에서 정점 A를 시작으로 DFS (Depth First Search, 깊이 우선 탐색) 했을 때,
올바른 탐색 순서는?

---

🌐 그래프 구조 다시 보기

     A
   / | \
  B  C  D
  |  |   \
  E  F    (C와 D 연결)
  |   \
      G

정점 연결 요약:

정점 연결된 정점

A	B, C, D
B	A, E, C
C	A, B, F, D
D	A, C
E	B, F
F	C, E, G
G	F

※ DFS는 깊게 파고들기, 가능한 한 한 방향 끝까지 감
그리고 방문한 노드는 다시 방문하지 않음

---

✅ DFS 실행 (시작 정점: A)

탐색 순서를 구체적으로 따라가 볼게요.
왼쪽 → 오른쪽 방향으로 연결된 정점을 방문한다고 가정합니다.

👉 A 방문

• 인접 정점: B, C, D 중 왼쪽부터 → B 선택

👉 B 방문

• 인접 정점: A(방문함), E, C
• → E 선택

👉 E 방문

• 인접 정점: B(방문함), F

👉 F 방문

• 인접 정점: C, E(방문함), G

👉 G 방문

• 인접 정점: F(이미 방문) → 백트래킹

백트래킹

• F → E → B → A
• 이제 B 다음 정점인 C 방문

👉 C 방문

• 인접 정점: A, B, F(방문함), D

👉 D 방문

• 인접 정점: A, C (모두 방문함)

🔚 끝!

---

🌟 최종 탐색 순서

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

---

✅ 정답

④ ABEFGCD ✅

---

🎓 결론 정리

개념 내용

탐색 방식	DFS (Depth First Search)
특징	한 방향 끝까지 탐색 후 백트래킹
주의	방문한 정점은 다시 방문하지 않음
정답	④ ABEFGCD

---