sukth09   2년 전

1부터 N개의 노드를 방문하면서 연결되어 있는 노드들을 다 방문하면서

방문여부를 체크해주고 각 dfs, bfs를 나오면 연결요소의 개수를 1개씩 증가시키는 알고리즘입니다.

제가 생각했을 때, dfs 와 bfs의 처리방식은 같다고 생각되는데,

bfs는 1204ms 시간이 소요되고

dfs는 260ms   시간이 소요됩니다.

대체 왜 시간이 1초씩이나 차이나는지 이유를 모르겠습니다 ㅠㅠ 도와주세요

아니면 제가 간과하고 있는 부분이 있을까요?

djm03178   2년 전

방문 체크는 큐에서 뺀 다음이 아닌, 큐에 넣을 때 해야 중복 방문을 하지 않습니다. 여러 정점에서 한 정점으로 동시에 들어가려고 할 수 있기 때문입니다.

그나저나 그게 시간 초과가 아니라니, 데이터 추가를 요청해야 할 것 같습니다.

sukth09   2년 전

아하!

매번 답변 감사합니다!! 다시한번 제출해보겠습니다

sukth09   2년 전

다시재출해보니 같은 시간으로 나오네요!!

하나배워갑니다 감사합니다!!

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