글 읽기 - 입력이 더 작은 비슷한 문제가 메모리초과 나는 이유?(union-find)

cyj89317 2년 전 0

1647번 도시 분할 계획을 크루스칼 알고리즘(union-find 사용)으로 풀었습니다.

1197번 최소 스패닝 트리는 단순히 최소 스패닝 트리를 구하는 거고, 1647번은 최소 스패닝 트리를 구해서 마지막에 추가한 간선만 빼주는 문제였습니다

입력의 경우 1197번은 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)이었고, 1647번은 각각 그보다 10배씩 많은 N은 정점의 개수 V(2 ≤ V ≤ 100,000)와 간선의 개수 E(1 ≤ E ≤ 1000,000)였습니다.

따라서 메모리 초과가 난다면 1647번일 것이라 생각했는데, 1197번에서만 메모리 초과 또는 런타임 에러 (InvalidPointer)가 났습니다...!!

1647에 제출한 코드를 그대로 답 부분 출력만 바꿔 주고 1197에 제출했는데, 1197이 메모리 초과가 나는 이유가 뭘까요?ㅜㅜ

#include <bits/stdc++.h>

using namespace std;

struct UnionFind {
	vector<int> parent, ran;
    UnionFind(int n) : parent(n), ran(n, 1){
    	for(int i = 1; i <= n; i++){
            parent[i] = i;
    	}
    }
    int f(int u){    // 부모 찾기
    	if( u == parent[u] ) return u;
    	parent[u] = f(parent[u]);
        return parent[u];
    }
    bool merg(int u, int v){    // 합치기
    	u = f(u); v = f(v);
        if( u == v ) return false;    // 만약 부모가 같으면 패스
        if( ran[u] < ran[v] ) parent[u] = v;
        else parent[v] = u;    // 랭크가 작은 쪽의 부모를 큰쪽으로
        if( ran[u] == ran[v] ) ran[u]++;    // 랭크가 같다면 한쪽 키우기
        return true;
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int n, m;
    cin >> n >> m;
    priority_queue< tuple<int, int, int>, vector<tuple<int, int, int>>, greater<> > pq;
    for(int i = 0; i < m; i++){
        int a, b, c;
        cin >> a >> b >> c;
        pq.push(make_tuple(c, a, b));
    }

    UnionFind uf = UnionFind(n);
    int ans = 0;
    //int last;
    while( pq.size() ){
        int c = get<0>(pq.top());
        int a = get<1>(pq.top());
        int b = get<2>(pq.top());
        pq.pop();

        if( uf.merg(a, b) ){
            ans += c;
            //last = c;
        }
    }

    //cout << ans-last << endl;
    cout << ans << endl;


}

sth3353 2년 전 1

7행에서 parent와 ran의 크기를 n이 아닌 n+1로 바꾸어주니 AC입니다.

cyj89317 2년 전 0

자답 합니다

처음 UnionFind를 만들 때 parent(n+1)로 해 줘야 했네요!! 1부터 n까지니까

1647번은 운이 좋아서 맞은 건지...

cyj89317 2년 전 0

헉 답변도 달렸군요 감사합니다!! ㅎㅎ

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

문제

문제

출처

ICPC

입력이 더 작은 비슷한 문제가 메모리초과 나는 이유?(union-find)

cyj89317 2년 전 0

sth3353 2년 전 1

cyj89317 2년 전 0

cyj89317 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말