girlera7   1년 전

안녕하세요. 처음에 bfs만으로 했다가 오류가 떠서, 여러 블로그 글을 보니 다들 

시간복잡도가 O(log(max(w)) * (N + M)) 라하더라구요. 

저는 처음에 이 문제를 bfs 만으로 풀 수 있다 생각을 했는데 시간 초과가 떠서 모든 경로를 탐색하기 때문에 그렇구나 라고 결론을 내렸는데, 알고리즘만 보면 bfs 부분이 똑같이 O( N + M) 인데, 왜 bfs 만으로는 시간초과가 나는 건지 잘 이해를 못하고 있습니다. 혹시, 제가 잘못 생각하는 부분이 있다면 지적해주시면 감사하겠습니다.

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