글 읽기 - 1197번 질문이요~! 최소신장트리 문제

plzrun 8년 전 0

아래와 같이 코드를 짰는데,

어느부분에서 에러인지 잘 모르겠습니다.

에러 케이스 하나만 짚어주실 수 없나요?

채점중 4%에서 '틀렸습니다' 뜨는데요,

밑에 just for the test 부분으로 주석처리되어있는거 해제하면

어떤 경로로 진행해서 답이나오는지 보여줍니다.

-------------------------------------------------------------------------------------------------------------------

코드에 대한 지적도 해주시면 감사해요. (바쁘시면 틀린 입력케이스만이라도 부탁드릴게요.)

해당 코드는 프림 알고리즘을 기반으로 작성했는데요,

s----->t (가중치 c)로 표현하였고, 이것을 inputE.target = t, inputE.cost = c를 한 다음

vector변수인 v에다가 v[s].push_back(inputE)를 하여 그래프를 구성하였습니다.

그래서 그래프 v[s][ i ]에서 i를 1씩 증가시키면서 s노드에 인접한 노드들의 번호와 가중치를 접근하고 그 가중치들로 minHeap을 구성하여 항상 최소가 되는 가중치를 뽑도록 했어요.

기타 자질구레한 예외사항들 처리한 부분은 continue 써져있는 부분입니다.

#include <stdio.h>
#include <queue>
#include <vector>
#include <limits.h>
#include <string.h>
#include <functional>
using namespace std;

struct Edge {
    int target;
    int cost;
    
    bool operator>(const Edge& rhs) const {
        return cost > rhs.cost;
    }
};

int main() {
    
    Edge minE, inputE;
    vector<Edge> v[100001];
    priority_queue< Edge, vector<Edge>, greater<Edge> > minHeap;
    bool marked[10001];
    memset(marked, false, sizeof(marked));
    
    int n, e;
    scanf("%d %d", &n, &e);
    
    //create a graph data structure
    int s=0, t, c;
    for(int i=0; i<e; i++) {
        scanf("%d %d %d", &s, &t, &c);
        inputE.target = t;
        inputE.cost = c;
        v[s].push_back(inputE);
        inputE.target = s;
        v[t].push_back(inputE);
    }
    
    //int k; //for a while loop
    //calculate the total cost of the M.S.T by using the 'Prim Algorithm' and the 'Min Heap' structure
    marked[s] = true;
    long long totalCost = 0;
    for(int i=s, cnt=0; cnt<n; cnt++) {
        for(int j=0; j<v[i].size(); j++) {
            if(marked[v[i][j].target]) continue;
            minHeap.push(v[i][j]);
        }

        if(minHeap.empty()) continue;
        minE = minHeap.top();
        minHeap.pop();
        
        if(marked[minE.target]) continue;
        //just for the test ----------------------------------------------------
        //k=-1; while(v[minE.target][++k].cost != minE.cost);
        //printf("%d-->%d\t%d\n", v[minE.target][k].target, minE.target, minE.cost);
        //----------------------------------------------------------------------
        marked[minE.target] = true;
        totalCost += minE.cost;
        i = minE.target;
    }
    
    printf("%lld\n", totalCost);
    return 0;
}

plzrun 8년 전 0

답변 감사합니다~!

plzrun 8년 전 1

@cubelover

덕분에 맞았습니다. ㅎ

혹시라도 질문 검색하실 분들을 위해 몇마디 적어보자면,

보니까 1--->2 (가중치1), 4--->2 (가중치1)인 경우

target(노드 번호를 의미):2, cost(가중치):1로 같은데도 불구하고 heap에 중복되게 삽입되는게 문제였어요.

일단은 heap이 비어있지 않으면 반복문을 계속 돌도록 해서 해결했는데,

중복 추가 자체를 안하게 한번 바꿔봐야겠습니다.

댓글을 작성하려면 로그인해야 합니다.