possible   1년 전

해당 문제 스크립트는 굉장히 불친절하다고 생각이 듭니다.

해당 문제를 풀 때 저같은 실수는 안 하셨음에 도움이 될만한 정보를 남깁니다.


문제에서 구하고자하는 정보는 1정점으로부터 N번 정점까지 가는 것입니다.

그 사이에 어떻게 하든 상관이 없고 1 -> ... -> N을 구하시면 됩니다.


그러면 어떻게 움직일 것이냐의 문제가 남습니다. 이것은 이득이 최대로 되는 경로로 움직이시면 됩니다.

즉, 두 갈래길이 있다고 할 때 왼쪽 길은 +100, 오른쪽 길은 +1 이라면 당연히 이득이 최대로 되는 쪽은 왼쪽이니.

단순하게 왼쪽을 고르시면 됩니다.

이런식으로 현 순간 최대가 되는 경로로 계속해서 움직이시는데, 잊지 말아야 하는 것은 최종적으로 N번 정점에 도달해야 하므로, 현재 경로가 N번 정점에 도달하지 못하면 현재 가고 있는 경로는 선택하시면 안됩니다.


다들 파이팅하시길 바랍니다.


참고) 태그는 벨만포드로 돼있는데, 저는 다익스트라로 풀었습니다.

kwakws0627   1년 전

"""

그러면 어떻게 움직일 것이냐의 문제가 남습니다. 이것은 이득이 최대로 되는 경로로 움직이시면 됩니다.

즉, 두 갈래길이 있다고 할 때 왼쪽 길은 +100, 오른쪽 길은 +1 이라면 당연히 이득이 최대로 되는 쪽은 왼쪽이니.

단순하게 왼쪽을 고르시면 됩니다.

이런식으로 현 순간 최대가 되는 경로로 계속해서 움직이시는데 ...

"""

 

말씀하신대로 매 순간 그리디하게 움직이면 아래 예제에서는 답이 어떻게 나와야 되나요??

제 생각에는 지금 당장은 조금 손해를 보더라도 우회를 해서 나중에 더 큰 이득이 되는 길을 선택하는게 낫다고 봅니다.

(1 -> 2 -> 3 -> 5 -> 6 총 이익 4)

possible   1년 전

제 스크립트만 읽고 구현하시면 그렇게 흘러가는 것이 맞습니다.

다만, 제가 그리디하게 설명드린 부분은 다익이 돌아가는 과정을 설명하기 위함이었고, 해당 부분은 pop되어 다음 정점을 골라가는 과정이 그리디하다 라고 말하고 싶었습니다.

다익스트라를 돌리게 되면 결국에는 이득이 최대가 되게끔 돌아가고, 사이클의 경우는 다른 모든 정점을 돌고 와서 다시 갱신될 수 있다는 점에서 한 정점이 최대 v번 재방문할 수 있다고 하였습니다.

답글 감사합니다 :)

possible   1년 전

조언 감사합니다!

저는 해당 글과는 다르게 음수 사이클이 있어도 더이상 줄어들지 않을 것입니다.

저는 다익스트라를 양수방향으로 짯기 때문입니다.

양수 방향으로 갈 때, 양수사이클은 한 정점을 최대 N번 도달한다는 점에서

O(E*Vlog(E))라고 생각했습니다. 해당 시간복잡도는 20000*100 * 15

=> 3*10^7 이 될 것입니다.


고로 시간초과가 나는 코드는 아니라고 생각했습니다.


다시 한 번 답변 감사합니다 :)

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