동점 간선이 있으면 항상 MST가 여러 개인가요? 유일성과 올바른 결과 검증은 어떤 조건으로 판단하나요?

꼬리 질문을 독립 문항으로 확장했습니다. 원래 문항에서 맥락 보기 →

잠깐, 답변을 보기 전에
먼저 내 말로 설명해 볼까요?

답변과 점검 포인트 펼치기답변 접기

구두 답변

정의를 외우기보다, 원리와 조건을 연결해 설명해 보세요.

모든 간선 가중치가 서로 다르면 MST 유일성이 보장되지만 동점이 있다고 반드시 여러 MST가 생기는 것은 아닙니다. 대체 간선으로 같은 비용의 다른 트리를 만들 수 있는 구조인지 봅니다.

동점에서 deterministic 간선 ID를 쓰면 결과 재현을 돕지만 최적성 증명은 별도입니다. 연결·cycle 부재·V-1 간선·최소 총비용을 검증하고 간선 목록 하나만 정답으로 고정하지 않습니다.

이해가 드러나는 지점을 확인해 보세요.

모든 간선 가중치가 서로 다르면 MST 유일성이 보장되지만 동점이 있다고 반드시 여러 MST가 생기는 것은 아닙니다. 대체 간선으로 같은 비용의 다른 트리를 만들 수 있는 구조인지 봅니다.
연결·cycle 부재·V-1 간선·최소 총비용을 검증하고 간선 목록 하나만 정답으로 고정하지 않습니다.

놓치기 쉬운 조건과 오해를 짚어 보세요.

다음 핵심 구분을 반대로 설명하거나 성립 조건을 생략한다: 모든 간선 가중치가 서로 다르면 MST 유일성이 보장되지만 동점이 있다고 반드시 여러 MST가 생기는 것은 아닙니다.

하나 더 질문하며 이해의 범위를 넓혀 보세요.

득점·감점 포인트는 학습용 자기 점검 기준이며, 특정 회사의 실제 채점표가 아닙니다.

답변을 보충하는 개념·예제·슈도코드를 읽어 보세요.