dudcks0994   3년 전

처음에 다익스트라로 푸는문제인거같아서 풀었는데 2퍼에서 무조건 틀리더라구요

그래서 해보다 계속 똑같길래 벨만포드로 풀었는데, n-1번 돌렸는데 92퍼에서 틀리는겁니다

그래서 뭐지??해서 n번 돌리니까 맞았습니다;;

왜 다익스트라로 안풀리는건지, 왜 벨만포드로 n-1번이 아닌 n번을 돌려야 하는건지 잘 모르겠습니다

j213h   3년 전

문제 자체는 다익스트라를 이용해도 맞는 문제이긴 합니다만, 틀리셨다고 하면 작성하신 코드가 잘못되지 않았나 싶습니다.

다익스트라에서 dist에 넣으신 초기값이 너무 작습니다.

간선이 최대 100000개에 가중치가 최대 100000이면 이론상 10^10까지 가능하지않을까요?

아래에 벨만-포드에는 초기값이 충분히 크게 작성되어있는 것으로 보아 그 문제일수도 있다는 생각이 듭니다!

dudcks0994   3년 전

아 저거 혹시나 너무크게줘서 그런가 싶어서 바꾼 상태였습니다!

1억 10억 100억했어도 안됐었습니다..

그리고 추가로

큐에다 넣을때 그리고 뺄때 거리에 곱하기 -1을 하는건 내림차순으로 정렬해주기 위해서 배운 방식을 쓴겁니다

근데 지금 친구코드와 비교해보고 혹시나 싶어 greater을 이용해 넣어줬더니 맞았습니다...

이유를 잘 모르겠습니다;; 간선이 0이 들어올수 있는것과 관계가있을거같은데...

j213h   3년 전

제가 그 부분을 못봤었네요.

저도 다익스트라로 풀이할땐 priority queue에 greater를 이용했습니다.

최소비용이니까 간선이 최소인 것부터 이용해야되기 때문이 아닐까 생각돼요.

C++ 입문한지 얼마 안되서 많이 부족하네요ㅠㅠ..

djm03178   3년 전

"간선이 0이 들어올수 있는것과 관계가있을거같은데..."

그렇습니다. 문제가 되는 곳은 q.pop()의 위치입니다. 간선의 가중치가 0일 수 있기 때문에 cur_node로부터 next_node를 거리가 같은 것으로 갱신할 수 있고, 그렇게 되면 q에 cur_dist와 같은 거리를 가진 다른 원소가 또 삽입됩니다. 만일 next_node (정점 번호)가 cur_node보다 크다면 pair의 비교 연산법에 의해 q의 top에는 next_node가 들어가 있을 것이고, 그래서 엉뚱한 원소를 pop하게 됩니다. q.pop()은 42번째 줄 직후에 있어야 합니다.

물론 거리의 초기값도 고치셔야 합니다.

djm03178   3년 전

그리고 그것만 바꾸면 시간 초과를 받게 되는데, 그 이유는 https://infossm.github.io/blog... 에서 찾으실 수 있습니다.

j213h   3년 전

작성하신 블로그 항상 잘 참고하고 있습니다. 감사합니다.

djm03178   3년 전

벨만 포드 코드의 문제점은 루프를 n-1번 돌렸느냐 n번 돌렸느냐의 차이가 아니라 100번째 줄의 조건이 잘못된 것입니다. dist[i]가 아니라 dist[from]을 검사해야 하며, 사실 이 조건문 자체가 아예 없어도 무방합니다. 루프를 한 번 더 돌렸더니 맞은 것은 그저 데이터상의 우연입니다.

dudcks0994   3년 전

djm03178

정말 너무감사합니다 선생님 블로그 글 한참들여다보고 이제서야 이해했습니다ㅠㅠㅠㅠ

다익스트라는 돌아가는걸 완전히 이해하는게 조큼 힘든거같네요... 플로이드나 벨만은 그래도 이해는됐는데...

너무 대단하십니다 커피한잔 사드리고싶습니다 여기 왜 쪽지기능이 없죠??

벨만은 이제보니 그렇네요... 출발하는 정점이 방문한 것만 돌리는거니까... 

너무너무 감사합니다!!!

djm03178   3년 전

추가로 greater로 바꾸신 코드 역시 로직에 문제가 있지만 데이터가 약해서 통과된 것이기 때문에 모두 데이터 추가 요청을 올렸습니다.

https://www.acmicpc.net/board/...

dudcks0994   3년 전

그럼 혹시 선생님 글 보고 수정한 이 코드도 틀린부분이 있을까요??

djm03178   3년 전

눈으로 대충 보기에는 괜찮아 보이네요.

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