다음과 같은 인접리스트로 표현된 그래프에 대해 노드 2를 시작 정점으로… | [7급 국가직 자료구조론] 07년 1회차 기출문제 상세 페이지

1[7급 국가직 자료구조론] 07년 1회차
다음과 같은 인접리스트로 표현된 그래프에 대해 노드 2를 시작 정점으로 너비우선탐색(breadth first search)을 수행했을 때 노드들의 방문 순서를 올바르게 나열한 것은?
문제 이미지
1
2 → 1 → 0 → 5 → 4 → 3 → 6
2
2 → 1 → 3 → 0 → 4 → 5 → 6
3
2 → 1 → 0 → 5 → 4 → 6 → 3
4
2 → 1 → 3 → 0 → 6 → 4 → 5
해설

노드 2에서 너비우선탐색을 하면 방문 순서는 2 → 1 → 3 → 0 → 6 → 4 → 5이다.

BFS는 큐를 쓰며 인접리스트에 적힌 순서대로 미방문 노드를 넣는다. 2의 리스트에서 1·3, 1에서 0·6, 3에서 4(2·6은 이미 방문), 0에서 5를 추가하므로 큐에 들어간 순서가 곧 방문 순서다.

  • 2 → 1 → 0 → 5 → 4 → 3 → 6은 1에서 0, 0에서 5로 깊게 내려간 깊이우선탐색의 순서다.
  • 2 → 1 → 3 → 0 → 4 → 5 → 6은 1의 이웃 6보다 3의 이웃 4를 먼저 방문해 큐 순서를 어겼다.
  • 2 → 1 → 0 → 5 → 4 → 6 → 3은 시작 정점과 바로 인접한 3을 마지막에 방문해 너비우선 원칙에 맞지 않는다.

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

이어서 풀어보기

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