livelysb1   7년 전

코드의 주석처럼 저의 코드는

뒷건물부터 시작해서 자기에게 오는 노드 방향으로 누적시간을 계산합니다.

해당 노드는 앞 연결 노드를 확인해서 자기를 통해서 노드에 도착한 것이 최대값인지 확인하고 최대값으로 변경해줍니다.

이렇게 앞으로 갈수록 최대값으로만 세팅을해서 완전탐색을 벗어난 BFS라고 생각하는데

왜 시간초과가 나올까요?

zlzmsrhak   7년 전

정상적인 BFS라면 queue에 각 노드가 단 한 번만 push되어야 하지만, 

이 코드에서는 노드까지의 거리가 갱신될 때 마다 push되기 때문에 한 노드가 여러번 push될 수 있으며,

시간복잡도가 O(N^2)을 넘어갈 수 있습니다.


위상정렬에 대해 찾아보시는 것이 문제 풀이에 도움이 될 것 같습니다.

livelysb1   7년 전

답변 감사합니다.

위상정렬을 공부해서 풀려고 하는데 코드도 너무 길어지고 시간복잡도가 효율적인지 잘 모르겠습니다. ㅠㅠ

조금더 팁을 주실 수 있나요?


혹시 제 코드에서 55번 push 가 여러번 될 수 있음을 감안해서 아래의 코드처럼 앞 건물은 한번만 push 되었고, 위상정렬의 순서대로 뒤에서 값은 변경해주되 push는 한번만 하는 코드로 변경하였습니다. 이번엔 왜 시간초과가 나올까요 ㅠ


zlzmsrhak   7년 전

contain 메소드의 시간복잡도가 선형이기 때문에 O(N^2)이 되어 시간초과가 나는 것 같습니다.

배열을 사용하거나 HashMap같은 container를 찾아보세요

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