k550706   1년 전

deque가 list보다 시간복잡도가 훨씬 낮다고 해서

BFS에 대한 강의를 듣고나서 이걸 BFS에 적용해봤는데

input 대신에 sys.stdin을 사용했고

graph에 append 하는 것(O(N))

graph와 visited 리스트를 생성하는 것 등은 시간복잡도가 적어보입니다.


i가 deque에 있는지 확인하는 작업을 삭제하고 로직을 변경하니 잘 됩니다.

index를 찾는 건 O(N)의 시간복잡도 아닌가요?

그럼 문제없이 되어야 하는거 같은데, 궁금합니다.

0000000000   1년 전

BFS의 기본 시간복잡도는 $O(V+E)$, 즉 이 문제에서 $O(N+M)$입니다. 그런데 여기에 N을 다시 곱하게 되면 시간 초과가 뜨겠죠.

또한 BFS/DFS에서 visited 체크는 큐에서 뺄 때가 아닌 큐에서 넣을 때 해야 합니다. 큐에서 넣을 때 visited 체크를 해 주면 아예 21행과 같은 처리를 할 필요 없이 한 정점은 한 번만 큐에 들어가게 됩니다.

k550706   1년 전

조언감사합니다.

BFS코드가 한결 간결해졌습니다!  

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