한국어
메뉴

자료 구조와 알고리즘

간선에 가중치가 없는 그래프에서, 출발점에서 각 정점까지의 최소 간선 수를 구하고 싶다. 적합한 탐색 방법과 그때 사용하는 자료 구조의 조합은?

  1. A너비 우선 탐색과 큐
  2. B깊이 우선 탐색과 스택
  3. C너비 우선 탐색과 스택
정답과 해설 보기

정답: A. 너비 우선 탐색과 큐

너비 우선 탐색은 출발점에서 간선 1개로 갈 수 있는 정점, 2개로 갈 수 있는 정점…처럼 가까운 순서로 방문합니다. 발견한 정점을 큐의 뒤에 넣고 앞에서 꺼내어 조사함으로써 이 '가까운 순서'가 유지되므로, 처음 도달했을 때의 간선 수가 그대로 최소 수가 됩니다. 깊이 우선 탐색(재귀나 스택을 사용)은 한 길을 갈 수 있는 데까지 나아가므로, 돌아가는 경로로 먼저 도달하는 경우가 있어 최단이 보장되지 않습니다. 큐 대신 스택을 사용하면 깊이 우선 탐색에 가까운 순회가 되어 버립니다.

이 분야 연습하기 분야로 돌아가기

자료 구조와 알고리즘의 다른 문제

  1. 간선에 방향이 없는 그래프에서 각 정점의 이웃 정점이 다음과 같다. A: B, C / B: A, D, E / C: A, F / D: B / E: B, F / F: C, E. 정점 A부터 재귀적인 깊이 우선 탐색을 수행한다. 이웃 정점은 여기에 쓴 순서로 조사하고, 아직 방문하지 않은 정점이 발견되면 바로 그 정점으로 나아간다. 정점을 방문하는 순서는?
  2. 간선에 방향이 없는 그래프에서 간선의 가중치(거리)가 S−A: 4, S−B: 1, A−B: 2, A−C: 1, B−C: 5, C−T: 3, A−T: 6이다. 다익스트라 알고리즘으로 S에서 T까지의 최단 경로를 구했을 때, 그 경로와 길이는?
  3. 다익스트라 알고리즘으로 올바른 최단 경로를 구하기 위한, 그래프에 관한 조건으로 올바른 것은?
  4. 작업 A~E에 'A는 C보다 앞', 'B는 C보다 앞', 'C는 D보다 앞', 'B는 E보다 앞', 'E는 D보다 앞'이라는 순서 제약이 있다. 모든 제약을 만족하는 작업의 순서(위상 정렬의 결과)는?
  5. 함수 f(x, y)를 'y가 0이면 x를 반환하고, 그렇지 않으면 f(y, x mod y)를 반환한다'로 정의한다. f(84, 36)을 호출했을 때의 반환값과, f가 호출되는 횟수(첫 호출 포함)의 조합은?