cororongtina   1년 전

도움이 될까 싶어 공유합니다.

Kruskal's alrogithm을 구현할 때, 제 코드처럼 vector를 사용했다면 반복문을 n번이 아닌, vector의 사이즈만큼(간선 개수만큼) 돌아야 합니다.

간선의 개수는 정점의 개수와 같지 않기 때문입니다.

저는 두 번째 반복문을 n번 반복해서 12%로 계속 틀렸었네요~ㅠㅠ

for (int i=0; i<n; i++) {
    for (int j=i+1; j<n; j++) {
        double dis = sqrt(pow(star[i].first - star[j].first, 2) + pow(star[i].second - star[j].second, 2));
        list.push_back({dis, i, j});
    }
}

sort(list.begin(), list.end());

double res = 0;
int edge_cnt = 0;
for (int i=0; i<list.size(); i++) {
    //kruskal's alrogithm 실행
}

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