벨만-포드 (1) 썸네일형 리스트형 [BOJ] 1219. 오민식의 고민 (18.8.22 그림 추가) 오민식의 고민클릭시 이동합니다. 어떻게 풀까? 으악... 저는 dfs와 bfs를 이용해서 풀었는데... 알고보니 벨만-포드 알고리즘이었어요.. 이따가 벨만-포드로 풀어서 해당 방법도 업데이트 하겠습니다. 버전 1과 2로 나누죠! Version.1 DFS and BFS 노드가 100개밖에 없으니 DFS를 이용해서 최댓값을 구해봅시다.잘 생각해보면, 해당 문제에서 양수 사이클이 생겨서 무한이 생기는 경우는, 방문했던 점을 또 방문할 경우에만 생깁니다.더 정확하게 말하면, 양수 사이클이 생겼을 경우이죠. 반대로, 음수 사이클이 생기는 경우에는 싸이클의 반복 경로를 탄다면, 가격이 계속 줄어든다는 것을 알 수 있죠!결국, 음수 사이클이 생기는 경우에는 반복 경로를 타지 않고 가는 것이 최대 수익을 얻는 경우입니.. 이전 1 다음
