9466번 - 텀 프로젝트
계속 84%에서 시간초과가 납니다....
어느 테스트케이스가 문제가 되는지 잘 모르겠어요...
일단 제 코드는 방문하지 않은 정점에 대해서 쭉 탐색하면서
정점들을 vector에 넣어주고요,
해당 사이클에서 방문된 정점과 만나면 그 방문된 정점에서부터 vector 끝까지에 담겨있는 정점들에게
얘네들은 사이클을 만들 수 있다고 표시해줘요.
그 다음 사이클을 못 만드는 애들의 갯수로 다 더해주면 된다고 생각을 했는데... 계속 84%인가 82%인가에서 시간 초과가 뜨네여ㅠㅠㅠ
코드를 어떻게 수정하는 방향으로 바꾸는 게 좋을까요?
--코드삭제--
만약
4 -> 1 -> 2 -> 3 -> 1
이런게 있으면 1번에서 1->2->3->1 을 찾아내고 4에서 1->2->3->1 을 또 찾겠죠?
그럼 극단적인 케이스로 1부터 50000까지가 사이클이고 나머지는 다 1번으로만 향한다고 했을 때, 시간복잡도는 거의 O(N^2) 가 될 것입니다. 그래서 시간초과가 날 것 같네요
한번 인지한 사이클은 더이상 보지 않도록 수정해보세요
정말 감사합니다!!
해결했어요~
댓글을 작성하려면 로그인해야 합니다.
nuclear852 7년 전
계속 84%에서 시간초과가 납니다....
어느 테스트케이스가 문제가 되는지 잘 모르겠어요...
일단 제 코드는 방문하지 않은 정점에 대해서 쭉 탐색하면서
정점들을 vector에 넣어주고요,
해당 사이클에서 방문된 정점과 만나면 그 방문된 정점에서부터 vector 끝까지에 담겨있는 정점들에게
얘네들은 사이클을 만들 수 있다고 표시해줘요.
그 다음 사이클을 못 만드는 애들의 갯수로 다 더해주면 된다고 생각을 했는데... 계속 84%인가 82%인가에서 시간 초과가 뜨네여ㅠㅠㅠ
코드를 어떻게 수정하는 방향으로 바꾸는 게 좋을까요?
--코드삭제--