글 읽기 - 런타임에러 [outofbounds] 질문드립니다...[C언어]

sc3289 2년 전 0

현재

1. 위상정렬

2. 각 node별 등수

3. 메모리를 사용해 불필요한 방문은 최대한 제거하면서 중복 방문 허용하며 bfs 진행

-> 등수가 target node보다 높으면(우선순위가 낮으면) 방문하지 않음

-> 방문하고자 하는 node에 저장된 value가 현재 타고온 경로의 value보다 해당 경로는 더 이상 진행하지 않음(동시에 건설이 가능했던 경로므로)

이런식으로 bfs로 완전탐색을 진행했으며, bfs돌릴때마다 큐는 초기화를 해뒀습니다. 배열또한 index를 다 꼼꼼하게 확인했는데...

어디서 터지는건지 모르겠습니다.

제일 의심스러운애는 int q[200000][2]; 이 부분인데,

중복방문은 허용하지만 불필요한 경우라고 판단되면 바로 컷하기 때문에 큐가 터질 것이라고는 생각되지 않습니다. 혹시 몰라서 200,000의 크기로 잡아주긴했지만... 똑같이 런타임에러가 뜹니다.

어디서 터지고 있는 걸까요?...

코드가 조금 난잡하긴 하지만 도움 부탁드립니다.

#pragma warning (disable:4996)

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

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


//tc input 부분 자료구조

int n; 
int target; // 건물의 수, 목표 건물
int time[1001]; // 각 건물을 짓는 데 걸리는 시간

node* list[1001]; // 건물 그래프 형성 list

void init();
void insert_node(int, int);
void free_mem();


//위상 정렬 부분 자료구조
int stack[1001];
bool visit[1001];
int top = -1;
void dfs(int);

int line[1001];
void make_line();


//실제 값 구하는 부분
int cost[1001];
int q[200000][2];
void bfs(int);


int main()
{
	int t;
	scanf("%d", &t);
	for (int i = 0; i < t; i++)
	{
		init();

		for (int j = 1; j <= n; j++) // 우선 순위 형성해주기
		{
			if (visit[j] == 0)
				dfs(j);
		}
		make_line(); // 위상 정렬에 따른 node 별 등수 저장해두기
		
		for (int j = top; j >= 0; j--) // target node보다 우선순위 높은애들을 시작점으로 bfs 돌려보기
		{
			if(cost[stack[j]] < time[stack[j]]) // 현재 건물을 짓는데 드는 비용보다 높아야 돌릴 가치가 있음.
				bfs(stack[j]);
			if (stack[j] == target)
				break;
		}
		printf("%d\n", cost[target]);
		free_mem();
	}
	return 0;
}

void bfs(int start)
{
	int front = 0, tail = 0;
	cost[start] = time[start];
	q[tail][0] = start;
	q[tail++][1] = time[start];
	while (front < tail)
	{
		if (q[front][0] == target) // 목적지 도달 했으니까 더 이상 볼 필요없음.
		{
			front++;
			continue;
		}
		if (q[front][1] < cost[q[front][0]]) // 진행할려는데, cost에 더 비싼 경로가 갱신되어있다?, 그럼 얘는 동시에 지을 수 있는 경로이므로 pass
		{
			front++;
			continue;
		}
		int cur_v = q[front][0]; // cur_v 까지 건설을 마친 상태
		int cur_cost = q[front++][1];
		node* cur = list[cur_v];
		while (cur != NULL)
		{
			if (line[cur->v] <= line[target])// target보다 등수의 크기가 작아야 선행 건물임
			{
				if (cost[cur->v] < cur_cost + time[cur->v])
				{
					cost[cur->v] = cur_cost + time[cur->v];
					q[tail][0] = cur->v;
					q[tail++][1] = cost[cur->v];
				}
			}
			cur = cur->next;
		}
	}
	return;
}

void make_line() // 각 등수 저장해두기
{
	int cnt = 1;
	for (int i = top; i >= 0; i--)
		line[stack[i]] = cnt++;
	return;
}

void dfs(int cur)
{
	visit[cur] = true;
	node* temp = list[cur];
	while (temp != NULL)
	{
		if (visit[temp->v] == 0) // 방문하지 않았던 지점이라면 방문해야지
			dfs(temp->v);
		temp = temp->next;
	}
	stack[++top] = cur;
	return;
}

void init()
{
	// 앞에서 썼던 자료구조들 초기화 해주기

	int k; // 우선 순위 입력 수
	scanf("%d %d", &n, &k);
	for (int i = 1; i <= n; i++) // 각 건물을 짓는데 걸리는 시간
		scanf("%d", &time[i]);
	int a, b;
	for (int i = 0; i < k; i++) // 각 건물별 우선 순위 입력
	{
		scanf("%d %d", &a, &b);
		insert_node(a, b);
	}
	scanf("%d", &target);
	return;
}

void insert_node(int a, int b)
{
	node* temp = (node*)malloc(sizeof(node));
	temp->v = b;
	if (list[a] == NULL)
	{
		temp->next = NULL;
		list[a] = temp;
	}
	else
	{
		temp->next = list[a];
		list[a] = temp;
	}
	return;
}

void free_mem()
{
	for (int i = 1; i <= n; i++)
	{
		if (list[i] == NULL)
			continue;
		node* cur = list[i];
		node* pre;
		while (cur != NULL)
		{
			pre = cur;
			cur = cur->next;
			free(pre);
		}
		list[i] = NULL;
	}
	for (int i = 1; i <= n; i++)
	{
		visit[i] = false;
		cost[i] = 0;
	}
	top = -1;
	return;
}

sc3289 2년 전 0

다시 드는 생각이지만.. in-degree를 이용해서 위상정렬을 했다면 bfs를 안쓰고 풀 수 있었을 문제네요..

하지만 혹시라도 위 코드에서 문제점을 찾아주신다면 좋겠습니다!.

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

문제

문제

출처

ICPC

런타임에러 [outofbounds] 질문드립니다...[C언어]

sc3289 2년 전 0

sc3289 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말