글 읽기 - 시간 초과가 나는 이유가 궁금합니다.

dongy12 5년 전 0

시간을 줄이기 위해서 visit 배열을 2차원 배열을 사용하니 메모리 초과가 떠서
지금 현 상황에서 최대한 시간을 줄일 수 있는 방법이 있는지 알고 싶습니다.

배열을 적게 사용하고 싶어서 visit배열에 단순히 방문 했는지 아닌 지 가 아닌

해당지점에 방문했을때 총 방문한 노드의 수를 저장하는 방식으로 해서 배열의

사용 개수를 줄였습니다.

쓸데없는 구간이나 좀 더 간단히 처리 할 수 있는 구간이 있으면, 알려주셨으면 합니다.

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

#define NMAX 10000
#define MMAX 100000

typedef struct node
{
	struct node *next;
	int data;
}NODE;
struct node *list[NMAX + 1]; 
int visit[NMAX + 1]; // 해당 배열에는 만난 노드의 갯수를 저장
int many[NMAX + 1]; // 시작점에서 만난 노드 갯수를 저장
int maxmeet = 0;    // 임시적으로 최대 만난 갯수를 저장

void link_List(struct node**p, int A, int B)
{
	struct node *temp = (struct node*)malloc(sizeof(struct node));
	temp->next = NULL;
	temp->data = A;
	temp->next = p[B];
	p[B] = temp;
}

void dfs(struct node **p, int start, int meet)
{
	struct node *temp;
	int data;
	temp = p[start];
	visit[start] = meet; // 만난 노드 값을 저장
	while (temp != NULL)
	{
		if (visit[temp->data] == 0) // 방문 체크
			dfs(p, temp->data, ++meet); // 미 방문시 방문값을 올리고 dfs실행
		temp = temp->next;
	}
	if (maxmeet < meet)
		maxmeet = meet;
}

void find_Max(int *max, int n)    // 최대 방문값을 찾는 함수
{
	int temp = 0;
	for (int i = 1; i <= n; i++)  // 최대값을 구함
	{
		if (temp < max[i])
			temp = max[i];
	}
	for (int i = 1; i <= n; i++) // 최대값과 같은 지점만 출력
	{
		if (max[i] == temp)
			printf("%d ", i);
	}
}
void many_Hack(struct node **p, int n)
{
	int check_node =0; // 시작점의 갯수를 체크
	int point;
	for (int i = 1; i <= n; i++)
	{
		if (p[i] != NULL)  // 연결된 지점이 있는지 확인
		{
			check_node++;  // 연결지점이 있을경우 최근의
			point = i;     // 시작지점을 저장
		}	
	}
	if (check_node > 1)             // 시작 가능 지점이 2개 이상일
	{                               // 경우 탐색 시작
		for (int i = 1; i <= n; i++)
		{
			memset(visit, 0, sizeof(visit));// visit배열을 초기화
			dfs(p, i, 1);
			many[i] = maxmeet;              //dfs로 나온 방문값을 저장
			maxmeet = 0;
		}
		find_Max(many, n);
	}
	else
		printf("%d", point);  // 시작 가능 지점이 1개 일 경우
}                             // 해당 지점 출력

int main()
{
	int n, m;
	int A, B;
	scanf("%d %d", &n, &m);
	for (int i = 0; i < m; i++)
	{
		scanf("%d %d", &A, &B);
		link_List(list, A, B);
	}
	many_Hack(list, n);
}

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

문제

문제

출처

ICPC

시간 초과가 나는 이유가 궁금합니다.

dongy12 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말