성우리뷰

2328)임시)런타임에러뜸)그래프의 해시

두원공대88학번뚜뚜 2020. 7. 21. 01:47

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

#define TRUE 1
#define FALSE 0
#define MAX 901
#define INF 5001

int stack[MAX];
int top = -1;
int hash[MAX];
int hashtop = 0;

void push(int value)
{
stack[++top] = value;
}

int pop()
{
return stack[top--];
}

int stacksize()
{
if (top < 0)
return 0;
else
return top + 1;
}

int getGCD()
{
int i, j;
int gcd = 1;
int minnum = INF;
int count;
int size = stacksize();

for (i = 0; i < size; i++)
{
if (stack[i] < minnum)
minnum = stack[i];
}

for (i = 2; i <= minnum; i++)
{
count = 0;
for (j = 0; j < size; j++)
if (stack[j] % i == 0)
count++;
if (count == size)
gcd = i;
}

return gcd;
}

int getLCD()
{
int i, j, cnt;
int lcm = 1;
int maxnum = 0;

for (i = 0; i < hashtop; i++)
{
if (hash[i] > maxnum)
maxnum = hash[i];
}

for (int i = 1; i < maxnum; i++)
{
cnt = 0;
for (j = 0; j < hashtop; j++)
if ((maxnum*i) % hash[j] == 0)
cnt++;

if (cnt == hashtop)
{
lcm = maxnum * i;
break;
}
}

return lcm;
}

void dfs(int from, int to, int**arr, int number, int* visit)
{
visit[from] = TRUE;

if (from == to)
{
int gcd = getGCD();
hash[hashtop++] = gcd;

return;
}

for (int i = 0; i < number; i++)
{
if (arr[from][i] > 0 && !visit[i])
{
push(arr[from][i]);
dfs(i, to, arr, number, visit);
visit[i] = FALSE;
pop();
}
}
}

int main()
{
int number;
scanf_s("%d", &number);

int ** arr;
arr = (int**)malloc(sizeof(int*) * number);
for (int i = 0; i < number; i++)
arr[i] = (int*)malloc(sizeof(int) * number);

int imsi = 0;
for (int i = 0; i < number; i++)
{
for (int j = 0; j < number; j++)
{
scanf_s("%d", &imsi);
arr[i][j] = imsi;
}
}
int * visit;
visit = (int*)calloc(number, sizeof(int*));

dfs(0, 1, arr, number, visit);

printf("%d", getLCD());
free(arr);

return 0;
}

///////////////////////////////////

지금 런타임에러 뜨는 상태