floydwarshall

Algorithm/Baekjoon Online Judge
[java] 백준 11780 (플로이드 2) Gold 3
Problem : https://www.acmicpc.net/problem/11780 11780번: 플로이드 2 첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 www.acmicpc.net Approach 플로이드와샬 알고리즘을 사용한 최단경로비용 구하기 + 최단경로를 구하는 문제이다. dist[i][j] = i부터 j까지 가는 최소비용이고, (i == j 일 경우거나, 도달할 수 없는 경우는 0) next[i][j] = j도착 직전 도시를 저장해놓은 배열이다. (i == j 일 경우거나, 도달할 수 없는 경우는 -1) 입력으로 그래프를 먼저 구성하고, 플로이드..
→2021.01.13
Algorithm/Baekjoon Online Judge
[java] 백준 1956 (운동) Gold 4
Problem : https://www.acmicpc.net/problem/1956 1956번: 운동 첫째 줄에 V와 E가 빈칸을 사이에 두고 주어진다. (2 ≤ V ≤ 400, 0 ≤ E ≤ V(V-1)) 다음 E개의 줄에는 각각 세 개의 정수 a, b, c가 주어진다. a번 마을에서 b번 마을로 가는 거리가 c인 도로가 있다는 의 www.acmicpc.net Approach 최단경로 사이클을 찾는 문제이다. 따라서 플로이드 와샬(Floyd Warshall) 알고리즘을 사용하여야 한다. 참고로 1:N 최단경로 문제는 다익스트라 알고리즘을, 음수사이클을 찾을 때엔 벨만-포드 알고리즘을, N:N 최단경로 문제는 플로이드 와샬 알고리즘으로 접근하면 용이하다. 이 문제에서는 각 노드 A에 대하여 A에서 시작하..
→2021.01.04
Algorithm/Baekjoon Online Judge
[java] 백준 11404 (플로이드) Gold 4
Problem : https://www.acmicpc.net/problem/11404 11404번: 플로이드 첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 www.acmicpc.net Approach 1 대 N 최단 경로를 구할 때에는 다익스트라(Dijkstra) 알고리즘을 사용하면 된다. N 대 N 최단 경로를 구할 때에는 플로이드 와샬(Floyd Warshall) 알고리즘을 사용하면 된다. 다익스트라 알고리즘은 가장 적은 비용을 하나씩 선택하며 최단경로를 구성해 나갔다면, 플로이드 와샬 알고리즘은 거쳐가는 정점을 기준으로 알고리즘을 수행한다. 다음과 같은 ..
→2021.01.03

• 이전
• 1
• 다음