https://www.acmicpc.net/problem/1738문제조건출발지부터 목적지까지 가야한다.단, 가는 경로에 깡패, 금품 두가지가 존재한다.목적지에 도착했을때, 금품의 양이 최대가 되는 경로를 구해라접근방법 다익스트라로 푸는 최단경로 문제인가? 라고 생각이 들었는데, 깡패가 금품을 갈취하면 음의 정수로 바뀌기 때문에, 다익스트라 알고리즘에서는 최단경로라고 판단된 노드는 더이상 갱신하지 않지만, 금품을 계속 반복해서 갈취당하면 음의 무한대로 짧아질수 있기 때문에 위 알고리즘은 아니다. 생각해보니 예전에 배웠던 음의 가중치가 있을때 최단거리를 구할수 있는 Bellman-Ford 알고리즘이 생각났다.Bellman-Ford 알고리즘 다익스트라 알고리즘과 더불어 최단경로를 구할 때 사용되는 대표적인 알..

https://www.acmicpc.net/problem/1162문제조건 N개의 도시가 주어지고 그 사이 도로와 이 도로를 통과할 때 걸리는 시간이 주어졌을 때 최소 시간이 걸리도록 하는 K개의 이하의 도로를 포장포장하게 되면 도로를 지나는데 걸리는 시간이 0서울은 1번 도시, 포천은 N번 도시 K개 이하의 도로를 포장하여 얻을 수 있는 최소 시간은?접근방법 가중치가 있는 그래프에서 특정지점에서 시작해서 다른지점까지의 최단거리를 구하는 알고리즘인 다익스트라가 떠올랐다. 사실 이 문제는 푸는것 자체는 크게 어렵지 않았다. 다익스트라 알고리즘 자체가 dp를 기반으로 이때까지 계산된 거리와 새로운 거리를 비교해서 계속해서 기록하는 구조이므로, 엄청나게 큰값이 들어 갈수 있기때문엥 21억이 넘는 수 까지 처리해..

https://www.acmicpc.net/problem/1446문제조건D킬로미터의 고속도로 길이 주어진다.지름길의 시작위치, 도착위치, 지름길의 길이가 주어진다.고속도로 끝지점까지 가는 최소거리를 구해라.접근방법 Brute Force로 봐야하나,,? 평소에 잘 접하지 않은 유형의 문제여서 당황스러웠다.최단거리를 구한다고 하면 다익스트라가 떠올랐지만 어떻게 적용시키지,,,? 계속 생각이 안나서 검색의 힘을 조금 빌렸다.  Dijkstra 최단경로를 구하는 대표적인 알고리즘이다.이중 for문을 이용한것과, priority_queue를 이용해서 구현을 선택할 수 있는데, 우선순위 큐가 시간복잡도가 훨씬 작으므로 우선순위 큐를 사용한다.알고리즘의 동작과정은 이와같다.방문하지 않은 노드 중에서 최단거리가 가장 ..