다익스트라3

• 

  [C++] 백준 - 11779 최소비용구하기2 (다익스트라) 1. 문제 2. 입출력 및 예제 3. 문제 해설 백준 - 1916 최소비용 구하기 문제와 비슷한 문제이다. 하지만 추가된 것은 몇 개의 노드를 거치면서 왔는 지에 대한 정보와 지나온 path에 대한 정보도 출력을 해야한다는 것이다. 처음에 예제 답안을 살펴보면 경로가 1 3 5로 나와있는 것을 확인할 수 있다. 하지만 위의 그래프를 그려보면 1 3 5 뿐만 아니라 1 4 5도 된다는 것을 알 수 있다. 그리고 경로에 대한 제약사항은 존재하지 않는다. 따라서 이 문제는 도달할 수 있는 경로가 여러가지일 경우에는 그냥 아무거나 출력하면 되는 문제였다. 여태까지 많은 경로를 기억했다가 출력하는 문제들을 풀어본 결과 경로를 기억하는 문제들은 대게 그 경로에 추가되는 로직이 있기 마련이다. 또한 위의 문제는 다익.. c++/알고리즘 2023. 2. 15.

• 

  [c++] 백준 - 특정한 최단 경로 1. 문제 2. 입출력 및 예제 3. 문제 해설 처음 이 문제를 읽었을 때 잘못 이해해서 얼마나 고생을 했던지... 나는 v1, v2를 이어주는 간선을 무조건 지나야한다는 줄 알고 처음에는 1 ~ v1, v2의 다익스트라를 1번 수행하고 N ~ v1,v2를 수행해서 1 ~ v1 + v1 ~ v2 + v2 ~ N과 1 ~ v2 + v2 ~ v1 + v1 ~ N 값 중 더 작은 값을 구하려고 했다. .. 다익스트라 2번이면 되었기 때문이다. 하지만 계속 틀렸다...! 그래서 왜일까 문제를 다시 읽어보니 v1, v2를 이어주는 간선을 무조건 지나가야 하는 것이 아니라 v1, v2를 그냥 지나가기만 하면 되었다. ... 그래서 생각 방향을 바꾸어 다시 생각을 해보니 이 문제가 오히려 갔던 길을 다시 가도 된다고.. c++/알고리즘 2023. 2. 6.

• 

  [c++] 다익스트라 알고리즘 (백준-최단경로 1753) 다익스트라 알고리즘이란? 다익스트라 알고리즘이란 한 지점에서 그래프 상의 나머지 모든 지점으로의 최단 경로를 구할 수 있는 알고리즘이다. 다익스트라 알고리즘은 그래프 상의 어느 한 간선의 가중치라도 음수가 존재하면 안된다. 이는 다익스트라 알고리즘이 현재 선택하는 것이 최선의 방법이라는 greedy를 기반으로 한 알고리즘이기 때문이다. 만약 음수의 가중치가 있다면 이 경로를 계속 지나갈수록 더욱 최선의 값을 가지게 되므로 다익스트라 알고리즘에 위배된다. (음수의 가중치를 가질 수 있을 때는 벨만 포드 알고리즘을 이용해야한다.) 다익스트라 알고리즘을 구현하기 위해서는 2가지의 과정을 반복해주면 된다. /* 1. 방문하지 않은 정점 중 가장 가중치 값이 작은 정점을 방문한다. -> 이를 위해 처음 배열을 무.. c++/알고리즘 2023. 1. 25.