Problem Solving
boj 1939 : 중량제한
1ssrek
2016. 8. 15. 17:58
boj 1939 : 중량제한
https://www.acmicpc.net/problem/1939
DFS+메모이제이션으로 어떻게 풀 수 있을지 고민하다가
그냥 BFS로 풀어제꼈다.
일반적인 BFS로 해결 가능하다. current번째 노드까지의 최대 무게를 flow[current]라 하면, current노드와 연결된 next 노드의 의 값, nextCost는 min(flow[current],edge(current,next) )이다. 최종적으로 초기화된 flow[next]값보다 nextcost값이 작다면 next와 nextcost의 쌍을 queue에 넣어준다.
최종적으로 queue가 빌 때까지 반복하면 각각 노드까지의 최대값을 구할 수 있다.