글 읽기 - 시간초과 에러나는데, 어디 부분이 문제일까요?

qptnnm 5년 전 0

DFS 로 위상정렬 알고리즘을 구현했습니다.

제출하면 시간초과가 나는데...

고수님들 어디 부분이 문제일지 조언 부탁드립니다.

==================================================

수정.

첫 번째 댓글 남겨주신 분의 조언에 따라 수정하였는데, 여전히 시간초과가 납니다..

#include <stdio.h>
#include <stdbool.h>
#include <malloc.h>

#define use_CRT_SECURE_NO_WARNINGS


typedef struct node
{
	int nodeNo;
	int indegree;
	struct node* next;
} NODE;

NODE nd[32001];
bool visited[32001];
int N, M;
int queue[32001];
int Q_cur, Q_size;

int dfs_cnt_cnt;
int dfs_cnt;

void DFS(int idx, int depth)
{
	dfs_cnt++;
	if (visited[idx] == true && depth == 1)
		return;

	visited[idx] = true;
	
	if (depth > 1)
		nd[idx].indegree--;

	if (nd[idx].indegree == 0 && depth != 1)
		queue[Q_size++] = idx;

	NODE* cur = &nd[idx];
	while (cur->next != NULL)
	{
		int nextIdx = cur->next->nodeNo;
		DFS(nextIdx, depth + 1);
		cur = cur->next;
	}
}

void DFS_Count(int idx, int depth)
{
	dfs_cnt_cnt++;
	
	if (depth > 1)
		nd[idx].indegree++;

	if (visited[idx] == true)
		return;

	NODE* cur = &nd[idx];
	while (cur->next != NULL)
	{
		int nextIdx = cur->next->nodeNo;
		DFS_Count(nextIdx, depth + 1);
		cur = cur->next;
	}

	visited[idx] = true;
}


void Run()
{
	// Count
	for (int i = 1; i <= N; i++)
	{
		DFS_Count(i, 1);
	}

	// Init and Find 0 indgree Vertexes
	for (int i = 1; i <= N; i++)
	{
		visited[i] = false;
		if (nd[i].indegree == 0)
		{
			queue[Q_size++] = i;
		}
	}

	// Main DFS
	while (Q_cur < Q_size)
	{
		int idx = queue[Q_cur++];
		DFS(idx, 1);
	}

}


int main()
{
	scanf("%d %d", &N, &M);

	for (int i = 1; i <= N; i++)
		nd[i].nodeNo = i;

	// Insert input
	for (int i = 0; i < M; i++)
	{
		int pre, post;
		scanf("%d %d", &pre, &post);
		NODE* tail = (NODE*)malloc(sizeof(NODE));

		// init tail node
		tail->next = NULL;
		tail->nodeNo = post;
		tail->indegree = 0;

		NODE* cur = &nd[pre];
		tail->next = cur->next;
		cur->next = tail;

	}

	Run();

	for (int i = 0; i < Q_size; i++)
		printf("%d ", queue[i]);

}

djm03178 5년 전 1

다른 곳은 보지 않았지만, 117번째 줄의 루프만 해도 최악의 경우 O(M^2)이 걸리므로 시간 초과가 날 수밖에 없습니다.

순서가 상관 없는 링크드 리스트라면 리스트의 맨 뒤까지 굳이 찾아가서 새 노드를 추가할 필요 없이, 새 노드를 헤드에 끼워넣어도 됩니다.

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

문제

문제

출처

ICPC

시간초과 에러나는데, 어디 부분이 문제일까요?

qptnnm 5년 전 0

djm03178 5년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말