rakyu888   10달 전

조금이라도 시간초과가 우려되는 부분이 있다면 가감없이 지적해주시면 감사하겠습니다.

djm03178   10달 전

존재하는 간선 정보만 가지고 돌려도 O(N(N+M))인데, 이 코드는 인접 리스트가 아닌 인접 행렬을 가지고 있어 DFS 한 번 당 존재하지 않는 간선을 포함하여 O(N^2)개의 간선을 확인하기 때문에 O(N^3)이 됩니다.

rakyu888   10달 전

말씀해주신 코멘트를 참고해서 인접 행렬을 인접 리스트로 바꿔서 DFS 한 번 당 존재하는 간선들만 확인하도록 바꿔봤습니다.

역시 시간초과가 나긴 하는데 language를 java -> java11 로 바꿔서 채점하니까 Pass가 뜨네요. 허허.. 이건 무슨 경우인지.

아래 코드의 경우, 존재하는 간선 정보만 가지고 돌렸으므로          O(N)                 *        O(N+M)    이 되는게 맞나요? ( myDFS() 부분 빅오 계산이 틀린 듯 합니다만.. )                                                                                                                   getTargetComputer()             myDFS()


djm03178   10달 전

언어 버전이 달라지면 내부 구현도 달라지니까 시간 차이는 충분히 발생할 수 있습니다.

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