특징을 확인해나가는 과정이 중요하다.
# solution to MST
MST의 솔루션이 몇개냐
좋은 점: 갯수를 계산할 수 있는 답이 있다.
나쁜 점: 너무 어렵다. (학부 수준x)
답이 유일할 조건 중 충분 조건을 알아보려고 한다.
(이런 경우에 답이 유일하다)
(답이 유일해서 이런 경우다 X)
Weight가 모두 다 다르면 답이 유일하다.
ex)
답이 유일하지만 Weight가 모두 다르지 않은 경우
당연한 거 아냐?
당연한 거 아님! 어려움!
엣지가 많을 경우 1,4를 선택하는 경우가 있을 수도 있고
2,3을 선택하는 경우가 있을 수도 있다.
(1,4를 선택하고 2,3을 선택하는 답이 있다면 1,2를 선택하는 답을 보여라~)
이 방법은 너무 어렵고
Prim and Kruskal Algorithm can find ANY Solution
= 모든 답을 커버한다.
답이 여러개인 경우가 있으면 찾을 수 있는 답이 모든 답일 수도 있고 아닐 수도 있다.
Prim and Kruskal Algorithm에는 Weight가 가장 작은 edge를 찾는 과정이 있었다.
(왼쪽 2를 고를수도, 오른쪽 2를 고를 수도 있다는 뜻)
choice를 다르게하면 답이 달라질 수 있으며 모든 답을 만들어낼 수 있다는 뜻
반면,
Stable Sort(같을 떄 입력에 있는 순서가 유지) 는 못찾는 답이 있을 수 있다.
2 3 1 2 3 2 => 1 2 2 2 3 3
답을 하나만 찾을 수 있다.
Kruskal Algorithm는
Tmst를 뭘 잡고 시작하던간에 알고리즘이 e대신 e'를 선택하게 만들면
최종적으로 다른 정답을 출력하게 할 수 있다.
Prim Algorithm도 마찬가지
알고리즘에 정답이 없는 엣지를 추가하면 사이클을 찾고 e대신 e'추가 가능했다.
=> 이것을 통해 증명(알고리즘이 이러니까 이런 일이 생긴다..특이)
모든 Weight가 다르면 Kruskal Algorithm이 진행되는 동안 선택권이 없음.
=> Kruskal Algorithm은 유일한 답을 생성한다.
반대로 Weight가 같은 것이 있다고 답이 여러개라고 얘기할 수는 없음
