jinsj1   4년 전

위상정렬을 접하고, 적용해보고 있으나

생각처럼 잘 되지가 않아, 도움을 요청합니다ㅠㅠ

bfs 방식으로 구현을 했으며
큐에 현 상태에 대한 cost를 저장하게 끔 했습니다.

okaybody5   4년 전

바로 넣자마자 틀렸습니다가 뜨는건가요??

jinsj1   4년 전

okaybody5 네 그렇습니다..ㅠㅠ


sgchoi5   4년 전

알고리즘 문제해결 전략같은 책을 보심이 어떨지..

jinsj1   4년 전

sgchoi5 먼저, 답변 감사드립니다

지금은 코드플러스 온라인 강의를 수강하고는 있어서, 정답 코드를 이해하면 되지만

매번, 제가 스스로 짠 코드에 대해서, 수정 및 해결이 안되더라구요.. 이게 알고리즘 시험을 볼때마다

이런 현상이 나타나서, 현재는 개념만 보고 스스로 짜보는 방식으로 진행하고 있습니다..

말씀하신 책대신 아직은 탑코더 알고리즘 트레이닝(빨간), 이 책을 반복해서 보고 있어요..

jinsj1   4년 전

자답입니다.
위상정렬도 가중 그래프이며,
가중 그래프의 최단 경로를 BFS로 구할 경우, 문제가 발생한다는 것을 깨달았습니다.(사실 책보고 알았습니다)
캡처.PNG

위와 같이 그래프가 존재할 때, A 부터 시작하게 되면

A - B,C 를 검사하고

A - C - B 의 경로를 확인할때, B는 이전에 검사했으므로 통과하게 되어

최종적으로는 A - B - D 의 결과를 출력하게 됩니다. (원래는 A - C - B - D 인데 말이죠)

따라서, 이를 해결하기 위해서

SPFA 를 쓰거나, 아니면 애초에 해당 노드까지의 cost를 '메모화 재귀' 로 저장하는

2가지의 방식이 있는 것으로 보이며, 저는 메모화 재귀를 이용해(백준님 코드를 이해하여) 해결했습니다.

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