백준 1922 - 네트워크 연결 (new 연산자의 사용)

[fezchoi]

백준 채점 시, 아래 코드에 대해 delete 연산자 사용 여부는 영향이 없었습니다!
62% 정도 이후에서 '틀렸습니다' 결과가 나오는 것으로 봐서는 예외 처리를 못한 탓인 것 같은데..
혹시 발견하시면 조언 부탁드리겠습니다.
감사합니다!

#include <iostream>
#include <algorithm>

using namespace std;

struct Edge {
    int src, dst, cost;

    Edge() { }
    Edge(int s, int d, int c)
        : src(s), dst(d), cost(c) { }
};

bool comp(Edge a, Edge b) {
    return a.cost < b.cost;
}

Edge* edgeList;
int* parent;

int _find(int a);
void _union(int a, int b);

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0);

    int N, M;
    cin >> N >> M;

    // alloc memory
    edgeList = new Edge[M];
    parent = new int[N + 1];

    // get input
    int src, dst, cost;
    for (int i = 0; i < M; i++) {
        cin >> src >> dst >> cost;

        if (src != dst) {
            edgeList[i] = Edge(src, dst, cost);
        }
    }

    // sort edge list
    sort(edgeList, edgeList + M, comp);

    // init parent
    for (int i = 0; i <= N; i++) {
        parent[i] = i;
    }

    // kruskal
    long long costSum = 0;
    int edgeCount = 0;
    for (int i = 0; i < M; i++) {
        if (edgeCount == M - 1) break;

        Edge edge = edgeList[i];

        if (_find(edge.src) != _find(edge.dst)) {
            _union(edge.src, edge.dst);
            costSum += (long long)edge.cost;
            edgeCount++;
        }
    }

    // print result
    cout << costSum << '\n';

    // flush
    delete[] edgeList; 
    delete[] parent; 

    return 0;
}

int _find(int a) {
    if (a == parent[a]) return a;
    else return parent[a] = _find(parent[a]);
}

void _union(int a, int b) {
    int pa = _find(a);
    int pb = _find(b);

    parent[pb] = pa;
}

[yjsohn]

크루스칼 알고리즘을 실행하는 for문에서 "edgeCount == M - 1"을 "edgeCount == N - 1"로 바꾸면 맞았습니다 뜹니다!

[fezchoi]

상당히 간단한 문제였군요.. 감사합니다 ㅠㅠㅠ

[wjdgns7712]

척척박사 @yjsohn님 sds-2021-summer-algorithm/java#13 혹시 이것도 도움주실수 있으실까요?ㅠㅠ

[HongyeongJu]

delete 여부는 상관없었군요 ! 저 부분 오타가 발생했었네요 ㅠㅠ...

[yjsohn]

@wjdgns7712 앗,, 척척박사라니 너무 과분한 칭찬이네요😖 감사합니다..ㅎㅎ 어려워보여서 손도 못댔던 문제라 코드를 보니 저도 정신이 혼미해지는데,, 일단 문제 풀어보게 되면 다시 한 번 확인해보겠습니다..! 근데 제 실력이 많이 부족해서 해결 못할 가능성이 높아보이네요..ㅠㅠ😭

[wjdgns7712]

cpp에도 new가 사용되는군요? 처음알았습니다...

[fezchoi]

추가적으로 발견한 사항인데, 실행시간은 비슷하지만 new 연산자로 1차원 배열을 사용하는 것이 priority queue보다 메모리를 적게 사용하네요!
가장 아래 제출한 코드가 priority queue를 사용한 kruskal 알고리즘이고,
가장 위 제출한 코드가 new 연산자로 1차원 array를 선언하여 사용한 kruskal 알고리즘 입니다!