BFS의 기본 시간복잡도는 $O(V+E)$, 즉 이 문제에서 $O(N+M)$입니다. 그런데 여기에 N을 다시 곱하게 되면 시간 초과가 뜨겠죠.
또한 BFS/DFS에서 visited 체크는 큐에서 뺄 때가 아닌 큐에서 넣을 때 해야 합니다. 큐에서 넣을 때 visited 체크를 해 주면 아예 21행과 같은 처리를 할 필요 없이 한 정점은 한 번만 큐에 들어가게 됩니다.
24444번 - 알고리즘 수업 - 너비 우선 탐색 1
BFS의 기본 시간복잡도는 $O(V+E)$, 즉 이 문제에서 $O(N+M)$입니다. 그런데 여기에 N을 다시 곱하게 되면 시간 초과가 뜨겠죠.
또한 BFS/DFS에서 visited 체크는 큐에서 뺄 때가 아닌 큐에서 넣을 때 해야 합니다. 큐에서 넣을 때 visited 체크를 해 주면 아예 21행과 같은 처리를 할 필요 없이 한 정점은 한 번만 큐에 들어가게 됩니다.
댓글을 작성하려면 로그인해야 합니다.
k550706 1년 전
deque가 list보다 시간복잡도가 훨씬 낮다고 해서
BFS에 대한 강의를 듣고나서 이걸 BFS에 적용해봤는데
input 대신에 sys.stdin을 사용했고
graph에 append 하는 것(O(N))
graph와 visited 리스트를 생성하는 것 등은 시간복잡도가 적어보입니다.
i가 deque에 있는지 확인하는 작업을 삭제하고 로직을 변경하니 잘 됩니다.
index를 찾는 건 O(N)의 시간복잡도 아닌가요?
그럼 문제없이 되어야 하는거 같은데, 궁금합니다.