글 읽기 - C++ 배열의 크기에 따라서 실행이 되지않는데 궁금합니다!

7slidemorning 2년 전 0

DFS , BFS 입문자 입니다.

스택과 큐를 배열로 구현하여 사용하고 있습니다. ArrMax는 1000으로 define 해놓았습니다.

그래프 또한 Matrix 형식으로 2x2 배열 선언을 통해 멤버 변수로 선언을 해놓았습니다.

문제는 ArrMax 를 100으로 define 했을때는 잘 실행이 되지만,

ArrMax를 1000 으로 define 하면 console 에는 아무런 출력이 나타나지 않고 종료됩니다.

메모리문제인것 같은데..... 어떻게 해결하면 좋을까요...??

LinkedList 뿐만이 답인가요??

#include <iostream>

#define ArrMax 1000

using namespace std;

class MyStack
{
private:
	int StackArr[ArrMax];
	int top;
public:
	MyStack() { top = -1; }
	bool isEmpty()
	{
		return (top == -1);
	}
	void push(int data)
	{
		top++;
		StackArr[top] = data;
		//cout << "push : " << data << endl;
	}
	int pop()
	{
		if (isEmpty())
		{
			cout << "ERROR : STACK IS EMPTY !" << endl;
			return -1;
		}
		else
		{
			//cout << "pop : " << StackArr[top] << endl;
			return StackArr[top--];
		}
	}
	int size() { return top + 1; }
	void print()
	{
		if (isEmpty())
		{
			cout << "Stack is Empty ! " << endl;
			return;
		}
		else
		{
			for (int i = 0; i < this->size(); i++)
			{
				cout << StackArr[i] << endl;
			}
		}
	}
};

class MyQueue
{
private:
	int QArray[ArrMax];
	int front; // front point first element
	int rear; // rear point last element index + 1
public:
	MyQueue()
	{
		front = rear = 0;
	}
	bool isEmpty()
	{
		return(rear == front);
	}
	void enQueue(int data)
	{
		QArray[rear] = data;
		//cout << "enQueue : " << QArray[rear] << endl;
		rear++;
	}
	int deQueue()
	{
		if (isEmpty()) { cout << "Queue is empty !" << endl; }
		else
		{
			//cout << "deQueue : " << QArray[front] << endl;
			return QArray[front++];
		}
	}
	void print()
	{
		for (int i = 0; i < (rear - front); i++)
		{
			cout << QArray[front + i] << endl;
		}
	}
};

class MyMatGraph
{
private:
	//int Matrix[ArrMax + 1][ArrMax + 1];
	int** Matrix;
	int vertex;
	bool* visit;
public:
	MyMatGraph()
	{
		vertex = 0;
		visit = NULL;
		Matrix = NULL;
	}
	MyMatGraph(int size)
	{
		Matrix = new int*[size + 1];
		vertex = size;
		visit = new bool[size + 1]; // don't use index 0 ,, 
		for (int i = 0; i < size + 1; i++)
		{
			visit[i] = false;
		}
		cout << "size : " << vertex << "create Matrix." << endl;
	}
	void InsertVertex() { vertex++; }
	void InsertEdge(int v1, int v2)
	{
		if (v1 > vertex || v2 > vertex) { cout << "ERROR : insert edge failed" << endl; }
		else
		{
			Matrix[v1][v2] = 1;
			Matrix[v2][v1] = 1;
		}
	}
	void VisitFlush()
	{
		for (int i = 0; i <= vertex; i++)
		{
			visit[i] = false;
		}
	}

	void dfs() { dfs(0); }

	void dfs(int StartVertex)
	{	
		int* travel = new int[vertex];
		int idx = 0;
		int whilecnt = 0;
		MyStack Stack;
		Stack.push(StartVertex);
		visit[StartVertex] = true;
		while (!Stack.isEmpty())
		{
			int dog = Stack.pop();
			//visit[dog] = true;
			for (int i = vertex; i > 0; i--)
			{
				if (Matrix[dog][i] == 1 && visit[i] == false)
				{
					visit[i] = true;
					Stack.push(i);
					//Stack.print();
				}
			}
			travel[idx] = dog;
			idx++;
			whilecnt++;
		}
		cout << "whilecnt : " << whilecnt << endl;
		cout << "dfs travel routine : ";
		for (int i = 0; i < vertex; i++)
		{
			cout << travel[i] << "->";
		}
		cout << endl;
		Stack.print();
	}

	void DFS(int StartVertex) 
	{
		cout << "DFS : ";
		MyStack Stack;
		Stack.push(StartVertex);
		while (!Stack.isEmpty()) 
		{
			int dog = Stack.pop();
			if (visit[dog] != true) 
			{
				cout << dog << " ";
				visit[dog] = true;
			}
			for (int i = vertex; i > 0; i--) 
			{
				if (Matrix[dog][i] == 1 && visit[i] == false) 
				{
					Stack.push(i);
				}
			}
		}
		cout << endl;
	}

	void BFS(int StartVertex) 
	{
		cout << "BFS : ";
		MyQueue Q;
		Q.enQueue(StartVertex);
		visit[StartVertex] = true;
		while (!Q.isEmpty()) 
		{
			int dog = Q.deQueue();
			
			for (int i = 1; i <= vertex; i++) 
			{
				if (Matrix[dog][i] == 1 && visit[i] == false) 
				{
					Q.enQueue(i);
					visit[i] = true;
				}
			
			}
			cout << dog << " ";
		}
		cout << endl;
	}
	void bfs(int StartVertex)
	{
		int* travel = new int[vertex];
		int jdx = 0;
		MyQueue Q;
		Q.enQueue(StartVertex);
		visit[StartVertex] = true;
		while (!Q.isEmpty())
		{
			int dog = Q.deQueue();
			//visit[dog] = true;
			for (int i = vertex; i > 0; i--)
			{
				if (Matrix[dog][i] == 1 && visit[i] == false)
				{
					visit[i] = true;
					Q.enQueue(i);
				}
			}
			travel[jdx] = dog;
			jdx++;
		}
		cout << "bfs travel routine : ";
		for (int i = 0; i < vertex; i++)
		{
			cout << travel[i] << "->";
		}
		cout << endl;
	}
	void printMat()
	{
		for (int i = 1; i < vertex + 1; i++)
		{
			for (int j = 1; j < vertex + 1; j++)
			{
				cout << Matrix[i][j] << " ";
			}
			cout << endl;
		}
	}
};

int main()
{
	MyMatGraph G(7);
	G.InsertEdge(1, 2);
	G.InsertEdge(1, 3);
	G.InsertEdge(1, 4);
	G.InsertEdge(2, 5);
	G.InsertEdge(2, 6);
	G.InsertEdge(3, 7);
	G.InsertEdge(4, 6);
	G.printMat();
	G.DFS(1);
	G.VisitFlush();
	G.BFS(1);
	

	return 0;

}

djm03178 2년 전 1

함수 내부에 선언되는 지역변수는 메모리 구조에서 스택 영역에 할당됩니다. 스택 영역은 프로그램마다 그 크기가 실행 시 정해져 있고, 예를 들어 VS에서 기본값은 1MB입니다. ArrMax가 1000이면 int Matrix[ArrMax][ArrMax]는 약 4MB 정도가 되기 때문에 할당하지 못하고 종료되는 것입니다.

스택 영역의 크기를 늘리는 옵션을 찾아보거나, 전역 변수를 쓰거나, 동적 할당을 하시면 됩니다.

7slidemorning 2년 전 0

정말 감사합니다 !!!! 많은걸 배우네요... :)

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

문제

문제

출처

ICPC

C++ 배열의 크기에 따라서 실행이 되지않는데 궁금합니다!

7slidemorning 2년 전 0

djm03178 2년 전 1

7slidemorning 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말