프로그래밍 공부 노트

https://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 각 도시를 노드로, 버스를 에지 혹은 순간이동 혹은 타임머신으로 본다면, 가중치가 음인 에지가 존재하고 가중치가 음인 사이클이 존재하는지 찾는 문제이므로 벨만-포드 알고리즘을 이용해 해결할 수 있다. #include #include #include using namespace std; typedef pair edge; typedef lo..

그래프 문제를 보다 보면, 특정 노드 a에서 노드 b까지의 경로를 구하는 문제가 자주 보인다. 이런 그래프에서 경로를 구하는 문제에 주로 사용하는 알고리즘이 다익스트라, 벨만-포드, 플로이드-워셜 알고리즘이다. 다익스트라는 그래프에 음의 가중치를 갖는 에지가 없을 때 주로 사용한다. 시작 노드에서 특정 경로를 이동해 노드 n에 도착했을 때의 비용을 cost[n]으로 나타낼 때, n에 연결된 i번째 에지 e_i와 e_i에 연결된 노드 n_i에 대해, n_i를 방문하지 않았다면 cost[n_i]가 cost[n] + e_i보다 작을 때 기존 경로를 시작 노드에서 n까지의 경로 + e_i로 갱신하면 더 적은 비용으로 n_i까지 이동할 수 있다. 이 과정을 알려진 경로가 존재하지 않을 때부터 시작해서 더 이상 갱..

https://www.acmicpc.net/problem/1865 1865번: 웜홀 첫 번째 줄에는 테스트케이스의 개수 TC(1 ≤ TC ≤ 5)가 주어진다. 그리고 두 번째 줄부터 TC개의 테스트케이스가 차례로 주어지는데 각 테스트케이스의 첫 번째 줄에는 지점의 수 N(1 ≤ N ≤ 500), www.acmicpc.net 음의 가중치가 존재하는 그래프에서 음의 가중치를 갖는 사이클을 탐지하는 문제이므로, 벨만-포드 알고리즘을 사용해 해결할 수 있다. 노드 i와 노드 j에 대해, 두 노드 사이의 에지의 개수가 한 개보다 많을 수 있다는 점과, i와 j가 같은 경우가 나올 수 있다는 점에 주의하자. #include #include #include using namespace std; typedef pair..