gearmamn06   2년 전

제가 생각한 아이디어는

우선 노드 1에서 방문할수 있는 노드들의 리스트가 있을때

이 노드들이 최초 노드 1에서 방문할 수 있는 노드임에 1로 복귀하기 이전 방문 가능한 노드라 판단하였습니다

예를들어 설명하면 1에서 방문가능한 노드가 2, 3, 4 이라고 할때, 노드 2, 3, 4를 순서대로

다익스트라를 이용하여 최단 경로를 구하는 최초 루프에서 제외합니다

가령 1로 복귀하기 바로 마지막 노드가 노드 2라고 가정을 하면 노드 1에서 2로 가는 값을 노드 2의 최단경로값에서 제외합니다.

이와같은 방법으로 2, 3, 4의 경우 각 노드의 최소값을 구하여 해당 노드에서 노드 1로 복귀하는 값을 구한 뒤

최소값을 구하여 문제를 풀려 하였습니다.

답은 잘 찾는것 같은데

8%부분에서 시간초과가 발생합니다.

다익스트라를 1에서 방문가능한 노드의 수마다 돌리기때문에 시간초과가 발생할수밖에 없는건가요?

gearmamn06   2년 전

친절하신답변 감사합니다!

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