gaelim   6년 전

위상정렬의 개념에 따라 코드를 작성했습니다. 초기에 조금씩 조금씩 수정하면서 수행했엇고 제출했을시 답안은 틀렸었지만 런타임에러는 안떴습니다. 그러나 단지 우선순위 배열 prior, 그리고 위상정렬의 선행 순위 indegree? 개념을 적용했는데 갑자기 런타임에러가 뜨면서  런타임이 어디서 에러가 났는지는 보이질 않습니다. 어떤것 이 문제일까요? 


#include <stdio.h>
#include <stdlib.h>
int t[1001], a[1001], deg[1001], prior[1001], head=0;
typedef struct queue{ int v; struct queue* next;}queue;
queue* q[1001];
void init(int a){
  q[a]=(queue*)malloc(sizeof(queue));
  q[a]->next=0;
  q[a]->v=0;
}
void push(int a, int b){
  queue* p = q[a];
  while(p->next) p=p->next;
  p->v=b;
  p->next=(queue*)malloc(sizeof(queue));
 // p->next->v=0; p->next->next=0;               <---------- 여기는 문제없어보입니다...
}
int main(){

  int T;
  scanf("%d", &T);
  while(T--){
    int n, k, ans;
    scanf("%d %d", &n, &k);
    for (int i=1; i<=n; i++){ scanf("%d", &t[i]); init(i);}
    for (int i=0; i<k; i++) {
      int u, v;
      scanf("%d %d", &u, &v);
      push(u, v);
      deg[v]++;
    }
    for (int i=1; i<=n; i++)
      if (!deg[i]) prior[head++]=i;

    //start                                                 <---------- 여기부터 주로 수정했었는데 런타임에러가 빵 떳습니다.
    for (int i=0; i<head; i++){
      for(queue* p= q[prior[i]];p;p=p->next){
        if(a[p->v]<t[prior[i]]+a[prior[i]]) a[p->v]=t[prior[i]]+a[prior[i]];
        deg[p->v]--;
        if(!deg[p->v]) prior[head++]=p->v;
      }
    }

    scanf("%d", &ans);
    printf("%d\n", t[ans]+a[ans]);
  }
}

gaelim   6년 전

재밌는 점은 제 GCC 컴파일러에서는 정상작동을 한다는 점입니다. 제가 문제 케이스의 숫자를 잘못 체크해서 배열을 작게잡았다 하더라도 위상정렬 개념을 적용하기 전까지는 33%에서 틀렸었는데 수정후 0%에서부터 런타임에러가 나면 ... 배열크기 문제는 아닌거같습니다.. 

djm03178   6년 전

그 문제가 없어보인다는 곳의 주석을 풀어야 할 것 같은데요. 거기를 주석처리해놓으면 리스트의 끝을 알 수 없기 때문에 이후에 push할 때 에러가 발생합니다.

djm03178   6년 전

그 문제가 아니라면 다음으로 체크할 곳은, head를 매 케이스마다 초기화를 안 해서 범위를 초과할 수 있어보이네요.

gaelim   6년 전

@djm03178 헤드 문제였습니다. ㅡ.ㅡ;;; 감사합니다. 하지만 역시 33%에서 틀렸네요 하지만 런타임 에러를 잡았기떄문에 한시름 놨습니다.. 감사합니다

gaelim   6년 전

이런 초기화 문제였네요 ㅠ.ㅠ. 테스트케이스가 여러개인데 배열들을 초기화하는걸 깜빡했네요..

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