글 읽기 - 아래 코드 중 어디가 틀렸는지 잘 모르겠습니다 ㅜㅜ

cjc83 7년 전 0

안녕하세요

고수님들 질문 있습니다.

아래 코드 중 어디가 틀렸는지 잘 모르겠습니다.

예제에 있는 두 문제는 Visual studio 상에서 정답이 자 나오는거 같은데..

어디가 틀렸는지 잘 모르겠습니다.

조언 부탁드립니다.

감사합니다.

#include <iostream>

using namespace std;

void printArray(int* A, int N)
{
	for(int i=0; i<N; i++)	
	{
		cout << A[i] << " ";
	}
	cout << endl;
}

void printGraph(bool** S, int N)
{
	for(int i=0; i<N; i++)	
	{
		for(int j=0; j<N; j++)
		{
			int temp = 0;
			if(S[i][j])
				temp = 1;

			if(j != N-1)
				cout << temp << " ";
			else
				cout << temp;
		}
		cout << endl;
	}	
	//cout << endl;
}

struct Stack
{
	int* data;
	int top;
};

struct Neighbor
{
	int size;
	int* idx;
};

void findIdx(bool* A, int N, Neighbor* nei)
{
	int size = 0;
	for(int i=0; i<N; i++)
	{
		if(A[i])
		{
			nei->idx[nei->size] = i;
			nei->size++;
		}

	}
}

bool isCircular(Stack* stack, int start_node)
{	
	for(int i=1; i<=stack->top; i++)
	{
		if(stack->data[i] == start_node)
		{
			return true;
			break;
		}
	}
	return false;
}

bool isPossiblePath(bool** S, int start_node, int end_node, int N, Stack* stack)
{
	
	Neighbor* nei = new Neighbor;
	nei->size = 0;
	nei->idx = new int[N];

	findIdx(S[start_node], N, nei);
	//printArray(nei->idx, nei->size);

	if(nei->size == 0)
		return false;

/*	if(start_node == end_node)		
		return true;*/	

	
	for(int i=0; i<nei->size; i++)
	{
		if(isCircular(stack, nei->idx[i]))
		{
			//printArray(stack->data, stack->top+1);
			return false;
		}

		// push
		stack->top++;
		stack->data[stack->top] = nei->idx[i];

		if(stack->data[stack->top] == end_node)
			return true;

		if(isPossiblePath(S, stack->data[stack->top], end_node, N, stack))
			return true;

	}
	// pop
	stack->data[stack->top] = -1;
	stack->top--;
	
	delete[] nei->idx;
	delete nei;

	return false;
}

int main() 
{

	//freopen("input2.txt", "r", stdin);
	int N;
	cin >> N;

	bool** S = new bool*[N];
	for(int i=0; i<N; i++)
	{
		S[i] = new bool[N];
		for(int j=0; j<N; j++)
			cin >> S[i][j];
	}
	
	//cout << "input" << endl;
	//printGraph(S, N);

	bool** result = new bool*[N];
	for(int i=0; i<N; i++)
	{		
		result[i] = new bool[N];
		for(int j=0; j<N; j++)
			result[i][j] = false;
	}

	for(int i=0; i<N; i++)
	{
		for(int j=0; j<N; j++)
		{
			/*if(i==j)
			{
				result[i][j] = true;
				continue;
			}*/
			//cout << "start_node: " << i << endl;
			//cout << "end_node  : " << j << endl;

			Stack* stack = new Stack;
			stack->top = -1;
			stack->data = new int[2*N];

			for(int k=0; k<N; k++)
				stack->data[k] = -1;

			stack->top++;
			stack->data[stack->top] = i;
			result[i][j] = isPossiblePath(S, i, j, N, stack);

			//printArray(stack->data,stack->top);

			delete[] stack->data;	
			delete stack;
		}
	
	}

	//cout << "result" << endl;
	printGraph(result, N);

	for(int i=0; i<N; i++)
		delete[] S[i];
	delete[] S;

	for(int i=0; i<N; i++)
		delete[] result[i];
	delete[] result;

}

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

문제

문제

출처

ICPC

아래 코드 중 어디가 틀렸는지 잘 모르겠습니다 ㅜㅜ

cjc83 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말