choah76   1년 전

1부터V까지 모든 정점에서 DFS를 실행하여 탐색합니다.

그래프 간선의 개수는 최대 V(V-1)개이므로 한번의 DFS에서 최대 V(V-1)개의 간선을 지나갑니다.

V개의 정점에서 DFS를 하므로, 최대 V*V*(V-1)번의 간선을 지나갑니다.

즉 시간복잡도가 O(V^3)이고, MAXV = 400이므로 시간 내로 풀린다고 생각헀으나, 시간초과를 받게 되었습니다.

제가 무엇을 잘못 알고 있는 것인가요?


추가로, 제 코드에서 어떤 부분을 고치면 시간이 더 줄어들 수 있을까요?

감사합니다.

zenith82114   1년 전

인접리스트가 아니라 인접배열이라서 그렇습니다.

DFS가 O(V+E)에 돌려면 각 정점에서 자기 간선 개수만큼만 시간이 걸려야 하는데 여기서는 무조건 O(V)씩 걸리죠.

choah76   1년 전

확실히 그것도 시간을 줄일 수 있겠네요

하지만 그래도 여전히 시간초과가 뜹니다..

제가 회로를 찾기 위해 28번째줄에서 visit[curr] = false를 추가하였는데, 아마 이것이 DFS를 너무 오래걸리게 하는 원인인 것 같습니다.

DFS로는 풀이가 어려울 것 같아서 플로이드워셜 알고리즘을 이용하였습니다.

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