Bellman-Ford

    [Java] 백준 1865 (웜홀) Gold 4
    Algorithm/Baekjoon Online Judge

    [Java] 백준 1865 (웜홀) Gold 4

    Problem : https://www.acmicpc.net/problem/1865 1865번: 웜홀 첫 번째 줄에는 테스트케이스의 개수 TC(1 ≤ TC ≤ 5)가 주어진다. 그리고 두 번째 줄부터 TC개의 테스트케이스가 차례로 주어지는데 각 테스트케이스의 첫 번째 줄에는 지점의 수 N(1 ≤ N ≤ 500), www.acmicpc.net Approach 문제에서 음수 사이클이 있는지를 물어보기에, 당연스럽게 벨만-포드 알고리즘을 시도해봤다. 벨만-포드 알고리즘은 시간복잡도가 O(VE) 인데, 간선의 개수가 V^2에 근사할 수 있으므로 최대 O(V^3)의 시간복잡도를 가진다. 이는 다익스트라 알고리즘의 시간복잡도인 O(V^2)보다 크지만, 음수 사이클을 판별해야 하는 문제에서는 다익스트라를 사용할 수 ..

    [java] 백준 11657 (타임머신) Gold 4
    Algorithm/Baekjoon Online Judge

    [java] 백준 11657 (타임머신) Gold 4

    Problem : 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 Approach 도시 to 도시 의 최단경로비용을 구하는 문제인데, 음수 사이클이 존재할 수도 있는 문제이다. 음수사이클이 존재할 수 있으므로, 다익스트라 알고리즘은 사용이 불가능하다. 문제에서 의도한 바는 벨만-포드(Bellman-Ford) 알고리즘이므로 필자도 그 방법을 이용했다. 벨만-포드 알고리즘은 최단거리로 목..

티스토리툴바