4Legs_Archives

문제 링크 : www.acmicpc.net/problem/1219 1219번: 오민식의 고민 첫째 줄에 도착 도시에 도착할 때, 가지고 있는 돈의 액수의 최댓값을 출력한다. 만약 오민식이 도착 도시에 도착하는 것이 불가능할 때는 "gg"를 출력한다. 그리고, 오민식이 도착 도시에 도착 www.acmicpc.net 벨만-포드 알고리즘에 대한 전반적인 이해가 필요한 문제이다. 이 문제를 막힘없이 해결할 수 있다면 벨만-포드를 잘 이해했다고 볼 수 있을 것이다. 기본적으로는 (도로를 지나며 사용하는 비용 - 도시에 도착해서 벌 수 있는 비용) 을 간선의 비용으로 두는 그래프에 대해 벨만-포드 알고리즘을 적용해 문제를 풀면 된다. (즉 수익의 최대화는 가중치의 최소화가 된다.) 하지만 문제의 조건에서 gg는 오..

문제 링크 : www.acmicpc.net/problem/11657 11657번: 타임머신 첫째 줄에 도시의 개수 N (1 ≤ N ≤ 500), 버스 노선의 개수 M (1 ≤ M ≤ 6,000)이 주어진다. 둘째 줄부터 M개의 줄에는 버스 노선의 정보 A, B, C (1 ≤ A, B ≤ N, -10,000 ≤ C ≤ 10,000)가 주어진다. www.acmicpc.net 벨만-포드 알고리즘을 이해하고 연습해볼 수 있는 문제이다. 벨만-포드 알고리즘에 대해서는 다음 포스트를 참조하자. 벨만-포드 알고리즘(Bellman-Ford Algorithm) [서론] 벨만-포드 알고리즘은 다익스트라 알고리즘과 마찬가지로 한 정점에서 출발하여, 다른 모든 정점에 대한 최단경로를 구하는 알고리즘이다. (다익스트라 알고리즘..

[서론] 벨만-포드 알고리즘은 다익스트라 알고리즘과 마찬가지로 한 정점에서 출발하여, 다른 모든 정점에 대한 최단경로를 구하는 알고리즘이다. (다익스트라 알고리즘 : 4legs-study.tistory.com/21) 하지만, 다익스트라 알고리즘에는 그래프에 음의 가중치가 없어야 한다는 조건이 있었다. 왜일까? 음의 가중치를 가진 간선이 존재한다면, 힙에서 한 정점을 꺼냈을 때 그 가중치 합이 해당 정점에 대한 최소 가중치 합임을 보장할 수 없기 때문이다. 다익스트라 알고리즘은 힙에서 꺼낸 정점에 대해 꺼낸 순간의 가중치 합을 최소로 고정한 후 (음의 가중치가 없다면 다른 어떤 간선을 추가로 지나오더라도 현재 가중치 합보다 작아질 수 없으므로) 다른 정점에 대해 해당 과정을 반복하는데, 음의 가중치를 가진..