cocobo123   3년 전

안녕하세요~~

c로 해서 인접행렬로 그래프 구현하고

dfs는 재귀, bfs는 큐로 구현해서 맞췄습니다.

그런데 4MS로 나와서 저두 0MS로 향상시키고 싶은데

다른 코드를 봐도 구현에 큰 차이가 없는 거같은데 어느 곳에서 속도를 향상시킬 수 있을까요???

아니면 단순히 c++ c의 차이일까요?? 궁금합니다.

jjwdi0   3년 전

DFS, BFS를 인접행렬로 구현하면 시간복잡도가 O(V2)이지만, 인접리스트로 구현하면 O(V+E)가 됩니다. (V는 정점 개수, E는 간선 개수)

문제에서 간선 개수의 상한이 10000개 이므로 인접 리스트로 구현하면 더 빠를 것 같네요.

cocobo123   3년 전

감사함돠

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