sos0911   12일 전

bfs로 접근을 시도했고

queue의 상태 공간에는 tuple=(현재 노드, 누적된 이동시간, 누적된 택시비)가 들어갑니다.

visited 벡터에 초기값=가진 돈+1로 설정해서 강의까지 남은 시간보다 tuple의 누적된 이동시간이 적거나 같고 visited에 저장된 돈보다 tuple의 누적된 택시비가 적을 경우 큐에 들어가게 했습니다.

뭐가 틀린 걸까요..??

lokilo   11일 전

5
150 1000
5
1 2 50 240
1 3 25 250
2 4 50 240
3 4 25 250
4 5 100 50

29dce502-33b3-4a4d-b25c-bbf9f2802047

lokilo   11일 전

아 추가적인 여담입니다만, 업로드 하신 소스를 제가 VS 2017 에서 돌렸을 때 BFS탐색하는 부분에서 temp값이 주소값이 건드려져서 인지 어떠한 이유인지는 모르겠으나 가끔 값이 변경되는 경우도 관측이 되었습니다. 제가 언어적인 부분은 잘 몰라서 정확한 답변은 못 드립니다 ;ㅅ;

sos0911   11일 전

와 진짜 감사합니다!

친절한 설명과 그림에 한번 더 감탄하고 갑니다.

생각해 보니까 저런 경우가 있었네요.

visited에 시간/cost 둘 다 저장해서 둘 중 하나라도 이득이면 지나가게 하는 게 맞는 것 같습니다.

temp값 변경은 c++ 초보라 잘 모르겠지만 auto&로 참조한 다음 그걸 pop 해버려서 그런 것 같습니다.

다시 한번 감사합니다!!

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