C++로 작성하여서 통과를 했습니다. 다만 시간이 다른 분들에 비해 많이 걸리더라구요 그래서 비교를 했는데 bfs를 거의 많이 쓰셨더라구요 그런데 dfs랑 bfs가 경우에 따라서 시간차이가 이렇게나 날 수 있나요?
그게 아니라면
제가 하나 추측하는 부분은 만약 테스트 케이스 중 하나가 노드가 1000개있고 1번노드부터 1000번까지 노드가 일직선으로 연결되어있는 트리형태이며 만약 명령어가 1000번에서 1번까지 거리를 구하라고 했을때 제 코드는 dfs 탐색을 현재 노드s에서 1번 노드 부터 1000번 노드까지 일일이 for문으로 도니까 이런 케이스의 경우에는 시간이 많이 걸릴 수 있겠더라고요 즉 1000번노드는 999번 노드으로밖에 연결되지않았는데 제코드는 일일이 1번노드부터 연결되어있나? 찾으니까 시간이 많이 걸릴수 있겠다 싶어서요.
rlagusrl0606 8달 전
C++로 작성하여서 통과를 했습니다. 다만 시간이 다른 분들에 비해 많이 걸리더라구요 그래서 비교를 했는데 bfs를 거의 많이 쓰셨더라구요 그런데 dfs랑 bfs가 경우에 따라서 시간차이가 이렇게나 날 수 있나요?
그게 아니라면
제가 하나 추측하는 부분은 만약 테스트 케이스 중 하나가 노드가 1000개있고 1번노드부터 1000번까지 노드가 일직선으로 연결되어있는 트리형태이며 만약 명령어가 1000번에서 1번까지 거리를 구하라고 했을때 제 코드는 dfs 탐색을 현재 노드s에서 1번 노드 부터 1000번 노드까지 일일이 for문으로 도니까 이런 케이스의 경우에는 시간이 많이 걸릴 수 있겠더라고요 즉 1000번노드는 999번 노드으로밖에 연결되지않았는데 제코드는 일일이 1번노드부터 연결되어있나? 찾으니까 시간이 많이 걸릴수 있겠다 싶어서요.