4386번 - 별자리 만들기
도움이 될까 싶어 공유합니다.
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 실행 }
댓글을 작성하려면 로그인해야 합니다.
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 실행 }