-
백준 5719 거의 최단경로알고리즘 문제/graph 2018. 2. 23. 05:11반응형
백준 5719 거의 최단경로
난이도 꽤 있다고 생각함.
다익스트라를 이용하여 최단경로를 저장해나가는데 pred 벡터에 이전 경로를 갱신해준다.
그리고 이전경로를 모두 탐색해 그 경로를 재귀적으로 접근하여 -~ 사용할 수 없는 간선으로 만든다.
그리고 다시 다익스트라를 활용한다.
그러면 거의 최단경로가 나온다.
개념적으로 와닿지만,
pred 를 어떻게 벡터로 만들고, ... 그리고 어떻게 삭제하는가... 에 대해서 생각하는데 시간이 많이 걸린 문제였다. 여기서 아마 구현능력과 논리력이 갈리었을거라 생각한ㄷㅏ
리저널,, 문제였는데 어렵긴 어려운것 같다. 난 제한 시간내에 못풀었다 100% ㅋㅋㅋ.
이 문제로 인해 느낀점은, pred 벡터에 target으로 갈 수 있는 여러 경로~ 그러니까 6으로 가는데에 최단경로로서 이전 vertex가 2 , 3 등이 존재할 수 있을 때 어떻게 pred에 동시에 저장해줄 것이냐... 가 질문일것이다. 이런것을 잘 구현해야할 것같다. 난 벡터로 했다.
소스보기
https://github.com/ingyeoking13/algorithm/blob/master/bj/p1000/5719.cc
반응형'알고리즘 문제 > graph' 카테고리의 다른 글
백준 11657 타임머신 (0) 2018.02.27 백준 5719 거의 최단경로 (0) 2018.02.23 백준 1766 문제집 (0) 2018.02.01 백준 2252 줄세우기 (0) 2018.02.01 백준 1005 acmcraft (0) 2018.02.01 백준 2623 음악프로그램 (0) 2018.02.01 TAG
