rlagusrl0606   8달 전

C++로 작성하여서 통과를 했습니다. 다만 시간이 다른 분들에 비해 많이 걸리더라구요 그래서 비교를 했는데 bfs를 거의 많이 쓰셨더라구요 그런데 dfs랑 bfs가 경우에 따라서 시간차이가 이렇게나 날 수 있나요? 

그게 아니라면

제가 하나 추측하는 부분은 만약 테스트 케이스 중 하나가 노드가 1000개있고 1번노드부터 1000번까지 노드가 일직선으로 연결되어있는 트리형태이며 만약 명령어가 1000번에서 1번까지 거리를 구하라고 했을때 제 코드는 dfs 탐색을 현재 노드s에서 1번 노드 부터 1000번 노드까지 일일이 for문으로 도니까 이런 케이스의 경우에는 시간이 많이 걸릴 수 있겠더라고요 즉 1000번노드는 999번 노드으로밖에 연결되지않았는데 제코드는 일일이 1번노드부터 연결되어있나? 찾으니까 시간이 많이 걸릴수 있겠다 싶어서요.

 

zenith82114   8달 전

인접 배열과 인접 리스트의 차이에 대하여 알아보시면 답이 될 것 같습니다.

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