글 읽기 - 메모리초과가 왜 날까요? 로직은 괜찮나요?

qktlf789456 3년 전 0

13퍼에서 메모리초과가 나네요 ㅠ matrix 로 2차원배열 동적할당으로 푸는문제는 아닌가요 ㅠ

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>



/*
테스트개수, Vertex, edge 가 각각 주어지고 edge 만큼이 주어진다
2
3 2
1 3
2 3
4 4
1 2
2 3
3 4
4 2
*/

int time;

int vertexSize;
int edgeSize;

char** matrix;
char* visited;
char* colored;

int dfs(int current) //이분그래프가 아니면 0 을 그즉시 반환
{
	visited[current] = 1;


	for (int i = 0; i < vertexSize; i++)
	{
		if (matrix[current][i] == 1 && visited[i] == 0)
		{
			if (colored[current] == 0)
				colored[i] = 1;
			else
				colored[i] = 0;

			dfs(i);
		}
		else if (matrix[current][i] == 1 && visited[i] == 1 && colored[current] == colored[i])
			return 0;

	}

	return 1;
}

int main()
{
	scanf("%d", &time);
	
	for (int _ = 0; _ < time; _++)
	{

		scanf("%d", &vertexSize);
		scanf("%d", &edgeSize);

		matrix = (char**)malloc(sizeof(char*) * vertexSize);
		visited = (char*)malloc(vertexSize);
		colored = (char*)malloc(vertexSize);

		for (int i = 0; i < vertexSize; i++)
		{
			visited[i] = 0;
			colored[i] = 0;
			matrix[i] = (char*)malloc(vertexSize);
			for (int j = 0; j < vertexSize; j++)
				matrix[i][j] = 0;
		}

		for (int i = 0; i < edgeSize; i++)
		{
			int a, b;

			scanf("%d", &a);
			scanf("%d", &b);

			a--;
			b--;

			matrix[a][b] = 1;
			matrix[b][a] = 1;
		}


		colored[0] = 0;
		
		for(int i = 0 ; i < vertexSize ; i++)
			if (dfs(i) == 0)
			{
				printf("NO");
				break;
			}
			else if(i == vertexSize-1)
				printf("YES");




		for (int i = 0; i < vertexSize; i++)
			free(matrix[i]);

		free(matrix);
		free(visited);
		free(colored);


		if(_ != time-1)
			printf("\n");

	}



	return 0;
}

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

문제

문제

출처

ICPC

메모리초과가 왜 날까요? 로직은 괜찮나요?

qktlf789456 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말