글 읽기 - 힙 정적 배열 VS 스택 정적 배열 segmentation fault

wlgh5014 1년 전 0

문제조건에 정점의 수가 1000개가 최대라서, 저는 인덱스를 1부터 시작하기 위해 1001로 설정했습니다.

혹시나 지정된 버텍스의 개수를 초과해서 변수가 증가하여, 범위밖의 메모리에 접근하는 지 종단점 찍어가면서 해봤는 데

제가 값으로 준 값 만큼만 오르고 그냥 함수 종료가 됩니다.

원인을 파악할 수가 없네요... 웃긴게 힙에 말고 그냥 메인 함수 내의 정적배열로 하니 시간초과입니다.

어차피 갈아 엎어야 하는 것은 맞는 데 도데체 무슨 차이죠? DFS를 재귀적으로 풀어서 그런가요?

ps: bfs를 좀 수정 했더니 77퍼에서 에러나네요.

//용어 혼동이 있어 수정 했습니다

#include <cstdio>
int IsVisited(int num, int visited[], int vertex);
void DFS(int** arr, int* index, int visited[], int startV, int vertex);
void BFS(int** arr, int index, int visited[], int WillVisit[], int startV, int vertex);
int DFS_index = 1;
int main()
{
	int** e = new int* [1001];
	for (int i = 0; i <= 1000; i++)
	{
		e[i] = new int[1001];
	}
	int visited[1001] = { 0, };
	int WillVisit[1001] = { 0, };
	int vertex, edge, startV;
	scanf("%d %d %d", &vertex, &edge, &startV);

	int v1, v2;
	for (int i = 0; i < edge; i++)
	{
		scanf("%d %d", &v1, &v2);
		e[v1][v2] = 1;
		e[v2][v1] = 1;
	}

	DFS(e, &DFS_index, visited, startV, vertex);
	printf("\n");
	for (int i = 1; i <= vertex; i++)
	{
		visited[i] = 0;
	}
	int BFS_index = 1;
	BFS(e, BFS_index, visited, WillVisit, startV, vertex);

	for (int i = 0; i <= 1000; i++)
	{
		delete[] e[i];
	}
	delete[]e;
}

int IsVisited(int num, int visited[], int vertex)
{
	for (int i = 1; i <= vertex; i++)
	{
		if (visited[i] == num)
		{

			return 1;
		}
	}
	return 0;
}

void DFS(int** arr, int* index, int visited[], int startV, int vertex)
{

	if (*index == 1)
	{
		visited[*index] = startV;
		printf("%d ", startV);
	}

	for (int i = 1; i <= vertex; i++)
	{
		if (*index == vertex)
		{
			break;
		}
		if (IsVisited(i, visited, vertex) == 0 && arr[startV][i] != 0)
		{
			(*index)++;
			visited[*index] = i;
			printf("%d ", i);
			DFS(arr, index, visited, i, vertex);
		}
	}

}

void BFS(int** arr, int index, int visited[], int WillVisit[], int startV, int vertex)
{
	if (index == 1)
	{
		visited[index] = startV;
		index++;
		printf("%d ", startV);
	}

	int index2 = 1;
	int temp = 1;
	while (index2<vertex)
	{
		for (int i = 1; i <= vertex; i++)
		{
			if (IsVisited(i, visited, vertex) == 0 && arr[startV][i] != 0)
			{
				WillVisit[index2] = i;
				index++;
				printf("%d ", i);
				index2++;
				visited[index] = i;
			}

		}
		startV = WillVisit[temp];
		temp++;
	}
}

wlgh5014 1년 전 0

저녁 되서야 해결하네요. 혹시 도움이 되실까 싶어 글을 씁니다.

첫째로 배열로 에지를 표현하실때 꼭 초기화 하세요. 안그러면 visited조건을 통과 해버려서 버텍스 개수보다 더 많이 출력 되는 수가 있습니다.

둘째로 조건을 제대로 구현하지 않으면 계속 돌다가 입력 값 높으면(많다라고 해야하나?) 세그폴트 에러가 뜨기도 합니다.

저는 bfs에서 에지나 버텍스 둘 중에 하나만 따졌는데, 1001번째 버텍스까지 접근을 해버리니 에러가 뜹니다. 당연히 당장 생각나는 반례는 다 이어진게 고작이라 애를 먹었넨요

마지막으로 노드가 끊기면 당장 종료하는 로직도 필요합니다.

2 1 1

1 2

3 4

다만 푸는 입장에서 당장 그러한 반례를 찾지 못해 저처럼 고생을 하게되고요.

글 읽기 - DFS와 BFS, 20%에서 구현이 틀렸습니다. (acmicpc.net) 여기 반례가 엄청 많아요. 여기 다 통과하시면 그냥 맞다고 봐도 될것같아요

포기마세요!

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

문제

문제

출처

ICPC

힙 정적 배열 VS 스택 정적 배열 segmentation fault

wlgh5014 1년 전 0

wlgh5014 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말