아 혹시

프림알고리즘에서 priority_queue를 이용해서 구현할때

음수 가중치 문제 때문인건가요?

그냥 저의 개인적인 생각입니다.

"프림 알고리즘"을 구현하는 것이 "크러스컬 알고리즘"을 구현하는 거 보다, 뭔가 더 길고 복잡하고 힘들어요...

그리고 여러 MST 문제를 풀면서, "크러스컬 알고리즘의 작동 원리와 정당성의 증명"을 묻는 문제는 봤지만, "프림 알고리즘의 정당성을 증명할 수 있니?"라고 물어보는 ㅜㄴ제는 보지 못한 것 같습니다.

마지막으로 여담입니다만, "프림 알고리즘"도 음수 가중치를 잘 처리할 겁니다.... 정 안된다면, 모든 간선의 가중치에 적당히 큰 상수를 더하면 해결되는 일인지라...

음 그렇군요

알겠습니다

외우기가 어러워요. 프림은..

프림 같은 경우, 제가 기억하기로는..

내가 선택한 정점의 집합 S가 있구 안 선택한 정점 S'이 있을 때

Q마다 S에서 S'으로 이어지는 것 중에서 최소 가중치를 갖는 걸 찾아야 하는데.

알고리듬 구조상 최소 힙이라는 게 들가야 하죠. 아마(?) 다익스트라를 최소 힙으로

구현하셨담 아시겠지만.. 비슷한 길이만큼 코딩을 해야 하죠. 좀 귀찮아요. 

거기에 인접 리스트까지. 허엌.. 극혐이무니다.

제가 복붙하고 빠르게 코딩하면 2-3분 정도면 되긴 하는데..

뭐 바꾸고 저거 바꾸고 하면.. 귀찮아염..

크루스칼은 정렬만 좀 외우고 find랑 merge 함수 (끽해봤자 7줄)만 외우면 금세 구현할 수 있죠.

이건 음.. 뭐랄까..

왜 간선이 연결된 상태를 표현할 때 왜 희소 행렬 안 쓰고

인접 리스트 쓰나요?? 같은 질문 같긴 한데요.

역시 마찬가지가 아닐까 싶네요. 

(프림은 솔직히 2-3번 쓰기라도 했지.. 희소 행렬은 여기서 써먹은 적이 아예 없는 거 같아요.)

그렇군요

이제 입문해서 저한텐 둘다 녹록치 않아서 별차이를 못느꼈었는데 ㅎ;;

많이 풀어보신분들말이 그렇다면 그런거겠죠

알겠습니다

그런데 크루스칼은 알고리즘의 작동원리를 물어보는 문제가 있을정도로 새련된 알고리즘인가요?

아 마지막으로 질문하나더..

다익스트라는 유니온 파인드를 베이스로 구현하는게아닌가요?

힙도 쓰는군요

실제로 프림을 구현한 간단한 코듭니다.

물론 priority_queue의 비교 함수 라던지 인접 리스트를 생성하는 code는 생략한 겁니다.

인접 리스트 만들고..

priority_queue의 비교 함수라던지 비교 구조체 같은 걸 정의한다면.

20 ~ 25줄 정도 되지 않을까 싶네요.

//0에서 시작한다.

poham[0] = 1;
for(int i=0;i<con[0].size();i++)
{
    I.from = i; I.to = con[0][i].to; I.n = con[0][i].cost; pq.push(I);
}

while(1)
{
    C=pq.top(); pq.pop();
    //from, to 둘 다 포함됨.
    if(poham[C.from] && poham[C.to])
        continue;
    cur = C.to;
    poham[cur] = 1;
    //cur로부터 연결된 간선들 정보 모두 넣기.
    for(int i=0;i<con[cur].size();i++)
    {
        if(poham[con[cur][i].to]) continue;
        pq.push(con[cur][i]);
    }
}

크러스컬 알고리즘으로 접근하면 풀리는데, 프림 알고리즘으로 접근하면 그냥 망해버리는 문제들이 있습니다.

당장 예는 떠오르지 않는데... 갓분들이 알려주시겠죠...?

..? 그건몰랐네요 호불호의 영역인줄알았는데

아예 틀리는문제가있다니

https://www.acmicpc.net/proble...

실력이 안좋아서 못풀거같긴하지만 ..;

좋은정보감사합니다

다들 감사합니다

오늘도 배우네요

다익스트라를 유니온 파인드로 구현한다는 야기는 첨 들어보는군요.

어느 부분부터 헷갈리시는지 잘 모르겠어용.. 일단 다익스트라는..

이건 애초에, 목적지 aaa로부터 bbb까지의 최단 거리를 구하는 거잖아요..

최소 힙으로부터 나온 정보가

uuu까지 최단 거리가 ttt다. 라고 해 봅시다.

그러면 uuu까지 최단 거리가 ttt보다 커질 일이 있을까요? 그럴 일이 없겠죵..

왜냐면 최소 힙의 특성상 최소 힙에 저장된 것들은

최소한 ttt보다 크거나 같은 녀석들이 집합일 거고.

uuu에서 aaa까지 가는 건 0보다 크거나 같으니까.. 실상 ttt보다 작아질 수 없겠죠.

그렇기 땜시 최소힙으로 구현하는 건 맞아요.

음수 가중치가 들어있을 때 

왜 최소힙으로 구현한 다익스트라가 왜 안 통하냐면..

굵게 친 부분이 성립하지 않아서 그래요. 잘 생각해 보세요..

아.. 답변해 주다 보니 생각난 건데

벨만포드하고 mcmf 같은 거 풀어제껴야 하는데..

머리가 안 되네요.. ㅠㅠ

아 다익스트라가 아니라 크루스칼..

이름을헷갈렸네요 ㅎ;;

아.. 잘못 치신 거구나.

맞습니다. 그냥 cost가 낮은 거 부터 높은 순으로 좌라락 훑어가면서 계산하죠.

a, b, cost가 있다면

이미 a와 b가 같은 집합에 있다면 추가하면 안 되구.

그렇지 않다면 추가해도 되구. 그런 거잖아요.

a와 b가 같은 집합에 있지 않으면 합쳐버리고..

그 과정에서 유니온 파인드가 쓰이는 거겠네요.