정답
최소비용신장트리의 간선 가중치 합은 128이다. 밑줄 친 ㉠은 사이클 생성을 방지하기 위해 필요하며, 간선 e(2,5)가 MST에 포함되었을 때 parent[1]=0, parent[5]=2이다.
출제 의도
이 문항은 크루스칼 알고리즘의 동작 원리, 특히 간선 선택 시 사이클을 방지하는 조건의 의미를 이해하고, 분리 집합(Union-Find) 구조에서 parent 배열이 어떻게 갱신되는지를 추적할 수 있는지를 평가한다.
풀이 과정
주어진 그래프의 모든 간선을 가중치 오름차순으로 정렬한 뒤, 크루스칼 알고리즘에 따라 사이클을 만들지 않는 간선만 선택한다.
가중치가 작은 간선부터 차례로 선택하면 다음과 같은 간선들이 MST에 포함된다.
11(0–1), 12(2–5), 14(4–7), 17(5–8), 18(3–4), 19(4–5), 20(0–3), 21(3–6)
총 9개의 노드이므로 MST는 8개의 간선을 포함하며, 이들의 가중치 합은
$$ 11 + 12 + 14 + 17 + 18 + 19 + 20 + 21 = 128 $$
따라서 최소비용신장트리의 간선 가중치 합은 128이다.
다음으로 (가)의 밑줄 친 ㉠인 if(v_set != u_set) 조건은, 선택한 간선의 양 끝 노드가 이미 같은 집합에 속해 있는지를 검사하는 부분이다.
이 조건이 없으면 이미 연결된 노드 사이의 간선도 MST에 포함되어 사이클이 형성되므로, 최소비용신장트리의 정의를 만족하지 못하게 된다. 따라서 ㉠은 사이클을 방지하기 위해 반드시 필요하다.
이제 (가)의 밑줄 친 ㉡을 통해 간선 e(2,5)가 MST에 포함되었을 때 parent 배열을 살펴본다.
set_union 함수는 두 노드 v, u 중 번호가 작은 쪽을 부모로 설정한다. 간선 e(2,5)가 선택되면, 2 < 5 이므로 parent[5] = 2가 된다.
또한 그 이전 과정에서 간선 e(0,1)이 선택되었으므로, 0 < 1에 의해 parent[1] = 0으로 설정되어 있다.
따라서 간선 e(2,5)가 MST에 포함된 시점에서 parent[1]과 parent[5]의 값은 순서대로 0, 2이다.
<풀이가 부정확할 수 있으니 반드시 교차검증 확인 바랍니다.>