글 읽기 - 런타임에러 원인을 도저히 못찾겠습니다...

hoy9090 6년 전 0

알고리즘은 그래프 방향을 역으로 뒤집어서 목표 건물부터 BFS를 돌려 가장 오래 걸리는 시간을 출력하였습니다.

질문들도 검색해보았는데 배열 크기 문제가 주원인인 것 같습니다.

제 코드에서는 queue[], free_arr[] 크기가 문제될 듯 한데

한 테스트 케이스에 k개의 규칙을 받는데 k가 100000 이하이므로 할당받는 노드 수도 100000 이하, 필요한 큐 크기도 100000 이하가 되지 않나요?

#include <stdio.h>
#include <stdlib.h>

typedef struct NODE {
  int node;
  struct NODE *next;
} NODE;

NODE *V[1001];
NODE *free_arr[100000];
int queue[100000][2];
int D[1001];
int max;
NODE *tmp;

int main() {
  int t, n, k, v1, v2, w, i, j, start, end, tmp2;

  scanf("%d", &t);

  while (t--) {
    start = 0;
    end = -1;
    j = 0;
    max = 0;
    scanf("%d %d", &n, &k);
    for (i=1; i<=n; i++) {
      scanf("%d", &D[i]);    // D: 건물 짓는 데 걸리는 시간
      V[i] = NULL;
    }
    for (i=1; i<=k; i++) {        //그래프 입력받는 구간
      scanf("%d %d", &v2, &v1);    // v2->v1
      if (V[v1] != NULL) {
        tmp = V[v1];
        while (tmp->next != NULL) {
          tmp = tmp->next;
        }
        free_arr[j++] = tmp->next = (NODE *)malloc(sizeof(NODE));
        tmp = tmp->next;
        tmp->node = v2;
        tmp->next = NULL;
      } else {
        free_arr[j++] = V[v1] = (NODE *)malloc(sizeof(NODE));
        V[v1]->node = v2;
        V[v1]->next = NULL;
      }
    }

    scanf("%d", &w);

    end++;
    queue[0][0] = w;
    max = queue[0][1] = D[w];

    while (start != end+1) {        // 지어야 하는 건물에서부터 BFS
      tmp = V[queue[start][0]];
      tmp2 = queue[start][1];

      if (tmp == NULL) {
        if (tmp2 > max)
          max = tmp2;
      }
      else {
        while (tmp != NULL) {
          end++;
          queue[end][0] = tmp->node;
          queue[end][1] = tmp2 + D[tmp->node];
          tmp = tmp->next;
        }
      }
      start++;
    }

    printf("%d\n", max);

    for (i=0; i<j; i++)    // 할당받은 노드 free
      free(free_arr[i]);
  }
  return 0;
}

djm03178 6년 전 0

중복 방문을 처리하지 못하기 때문에 문제가 됩니다.

아래 예시는 1번부터 4개 단위로 다이아몬드 형태로 연결되어 있고, N번부터 탐색을 시작하는 케이스입니다.

1
80
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
2
3
4
4
5
6
7
7
8
9
10
10
11
12
13
13
14
15
16
16
17
18
19
19
20
21
22
22
23
24
25
25
26
27
28
28
29
30
31
31
32
33
34
34
35
36
37
37
38
39
40
40
41
42
43
43
44
45
46
46
47
48
49
49
50
51
52
52
53
54
55
55
56
57
58
58
59
60
61
61
61

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

문제

문제

출처

ICPC

런타임에러 원인을 도저히 못찾겠습니다...

hoy9090 6년 전 0

djm03178 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말