rudxo007   7년 전

방향성 제시 부탁드립니다.

createNode 함수를 만들어서 linked-list 에 저장을 하였습니다.

그리고 dfs 함수를 이용해서 목적지까지 가는 경로의 값을 비교해서 구현 하려고 생각하고 있습니다.

dfs 구현하는데 있어서 조건을 어떻게 줘야하고 어떤식으로 나아가야할지 좀 막막한 상황입니다.

도와주시면 감사하겠습니다.

sgchoi5   7년 전

저는 알고리즘 문제 해결전략에 있는 위상 정렬하는 문제 참고해서 우선 위상 정렬 결과를 만들어 냈고요..


vector 결과를 reverse() 할 필요없이 처음부터 W 를 찾아서 W를 찾으면 그 때부터 DFS + Memoization 으로 vector 의 끝까지 가면서
최대 비용을 찾았습니다.

vector 에서 W 다음 위치부터, 이 원소를 향하는 모든 원소를 dfs 로 들어가는 것을 반복하면서 뒤로 돌아면서 건설비를 더 합니다 ( dfs / memo 의 전형적인 형태로 )


cost[i] 가 i 번째 지점의 건설비라고 하면 dp[i] 는 i 번째까지의 건설비 중 최대값으로 했습니다.


plzrun 님의 또 다른 설명과 TC 19개는   =>   https://www.acmicpc.net/board/... 

rudxo007   6년 전

sgchoi5 님 감사합니다.

이제야 코드를 짤 수 있을거 같습니다. 후

정말 도움 감사드려요 늦었지만 ㅜ

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