시작 정점이 6일 때, 다음 그래프에 대한 깊이 우선 탐색(DFS: D… | [7급 국가직 자료구조론] 18년 1회차 기출문제 상세 페이지

1[7급 국가직 자료구조론] 18년 1회차
시작 정점이 6일 때, 다음 그래프에 대한 깊이 우선 탐색(DFS: Depth First Search)의 방문 순서는? (단, 인접한 정점들은 오름차순으로 방문한다)
문제 이미지
1
6, 5, 3, 1, 0, 2, 4, 7, 8, 9
2
6, 5, 7, 3, 8, 9, 1, 4, 0, 2
3
6, 5, 3, 4, 2, 1, 0, 7, 8, 9
4
6, 5, 7, 3, 1, 4, 0, 2, 8, 9
해설

정점 6에서 인접 정점을 오름차순으로 방문하는 DFS의 방문 순서는 6, 5, 3, 1, 0, 2, 4, 7, 8, 9이다.

6의 인접 정점(5, 7) 중 작은 5로 가고, 5에서 3, 3에서 1, 1에서 0으로 내려간다. 0은 더 갈 곳이 없어 되돌아가(backtracking) 1의 다음 인접 정점 2, 이어서 4를 방문한다.

4의 인접 정점은 모두 방문했으므로 5까지 되돌아가 7을 방문하고, 7에서 8, 9 순으로 방문하면 탐색이 끝난다.

  • 6, 5, 7, 3, 8, 9, 1, 4, 0, 2: 시작 정점에서 가까운 정점부터 차례로 방문한 너비 우선 탐색(BFS)의 순서이다.
  • 6, 5, 3, 4, 2, 1, 0, 7, 8, 9: 3의 인접 정점 중 1이 4보다 작으므로 1을 먼저 방문해야 한다.
  • 6, 5, 7, 3, 1, 4, 0, 2, 8, 9: 5에서 3이 7보다 작은데 7을 먼저 방문해 오름차순 조건에 어긋난다.

오류나 개정된 내용이 보이면 알려주세요

이어서 풀어보기

[7급 국가직 자료구조론] 18년 1회차 20문항 이어서 보기문제·정답·해설을 한 페이지에서 이어서 볼 수 있어요7급 국가직 자료구조론 기출문제 암기장 전체 보기