📚 알고리즘/다익스트라
[백준 4485] 녹색 옷 입은 애가 젤다지?_다익스트라(c++)
[문제] https://www.acmicpc.net/problem/4485 4485번: 녹색 옷 입은 애가 젤다지? 문제 젤다의 전설 게임에서 화폐의 단위는 루피(rupee)다. 그런데 간혹 '도둑루피'라 불리는 검정색 루피도 존재하는데, 이걸 획득하면 오히려 소지한 루피가 감소하게 된다! 젤다의 전설 시리즈�� www.acmicpc.net [접근법] 다익스트라인지 몰랐지만 다익스트라로 풀었다! [문제풀이] 다익스트라는 하나의 정점에서 다른 모든 정점들의 최단경로를 구하는 알고리즘이라고 한다. 첫 정점을 기준으로 연결되어 있는 정점들을 추가해가며 최단거리를 갱신해야 한다고 한다. bool 배열로 방문체크를 해주지 않아도 dist배열만으로 탐색을 한다. dist배열을 큰 값으로 초기화해두고 이동을하면서 a..