글 읽기 - 계속 런타임 에러가 나네요 ㅜㅜㅜ

bklove91 6년 전 1

20%정도 채점되다가 런타임 에러가 뜨네요..

도대체 뭐가 문제일까요.. 도와주세요 ㅜㅜ

#include <stdio.h>
int K;
int V, E;
int p, q;
int check = 1;
int end = 0;
int adj[20001][20001];
int color[20001];
void init();
void dfs(int v);
int paint();

int main(int argc, const char * argv[]) {
    scanf("%d", &K);
    while(K--){
        scanf("%d %d", &V, &E);
        init();
        for(int i = 1; i <= E; i++){
            scanf("%d %d", &p, &q);
            adj[p][q] = adj[q][p] = 1;
        }
        for(int i = 1; i <= V; i++){
            if(color[i] == -1){
                if(end == 1) break;
                dfs(i);
            }
        }
        if(end == 1) printf("NO\n");
        else printf("YES\n");
    }
    return 0;
}

void init(){
    end = 0;
    for(int i = 1; i <= V; i++){
        color[i] = -1;
        for(int j = 1; j <= V; j++){
            adj[i][j] = 0;
        }
    }
}

void dfs(int v){
    color[v] = paint();
    for(int i = 1; i <= V; i++){
        if(adj[v][i] == 1){
            if(color[i] == color[v]){
                end = 1;
                break;
            }
            if(color[i] == -1) dfs(i);
        }
    }
}

int paint(){
    if(check == 1) check = 0;
    else check = 1;
    return check;
}

djm03178 6년 전 2

int = 4바이트

20000 * 20000 = 4억

adj ~= 16억 바이트 ~= 1.49GB

jupiny 6년 전 1

메모리 초과 문제라면 왜 처음엔 에러가 발생하지 않고 20%에서만 나타나는 걸까요??

djm03178 6년 전 2

아마도, 운영체제가 메모리를 처음부터 다 할당해주고 시작하는 것이 아니라, 실제로 접근하려는 시도가 있을 때까지는 할당을 보류해두었을 거라고 생각되네요. 정점의 수가 적을 때는 높은 인덱스에 접근할 일이 없었을 테니 문제 없이 넘어간 듯하고요.

jupiny 6년 전 1

아 그럴 수도 있나보군요. 컴파일할 때 배열의 크기만큼 항상 처음에 할당되는 거라 생각했었네요.

답변 감사합니다 :D

bklove91 6년 전 0

답변해주셔서 감사합니다

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

문제

문제

출처

ICPC

계속 런타임 에러가 나네요 ㅜㅜㅜ

bklove91 6년 전 1

djm03178 6년 전 2

jupiny 6년 전 1

djm03178 6년 전 2

jupiny 6년 전 1

bklove91 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말