![]()
📍 정의 및 특징 모든 노드 간 최단 경로 탐색 - 음수 가중치 에지가 있어도 수행 가능 - DP 원리 이용 (점화식) D[S][E] = Math.min(D[S][E], D[S][K] + D[K][E]) : A → B까지 최단 경로를 구할 때, 최단 경로 위에 K가 존재한다면 그것을 이루는 부분 경로 역시 최단 경로 - 노드 개수의 범위가 적은 경우 사용 (∵ 시간 복잡도가 빠른 편이 아니므로) - 시간 복잡도 : O(V³) 📍 필요 변수 1. 최단 거리 배열 2. 인접 행렬 📍 실행 과정 최단 거리 배열 선언 · 초기화 - D[S][E] = if(S == E) ? 0 : ∞ 최단 거리 배열에 인접 행렬 사용해 그래프 데이터 저장 플로이드-워셜 수행 : 점화식으로 배열 업데이트 → 3중 for문 ➕ 예제..
![]()
📍 종류 1) BFS - 가중치 X / 단순 최단 경로 탐색 2) 다익스트라 - 가중치 O / 한 노드 기준 모든 노드와의 최단 경로 탐색 3) 플로이드-워셜 - 상관 X / 모든 노드 기준 모든 노드 간 최단 경로 탐색 (사실상 그냥 dp) 4) 벨만 - 포드 - 가중치 O / 특정 출발 노드 → 다른 모든 노드까지의 최단 경로 탐색 (참고) [백준 1753] 최단경로 -Java코드 (Dijkstra)★★★ https://www.acmicpc.net/problem/1753 1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘 bangu4.tistory.com
![]()
🔺 문제 1389번: 케빈 베이컨의 6단계 법칙첫째 줄에 유저의 수 N (2 ≤ N ≤ 100)과 친구 관계의 수 M (1 ≤ M ≤ 5,000)이 주어진다. 둘째 줄부터 M개의 줄에는 친구 관계가 주어진다. 친구 관계는 A와 B로 이루어져 있으며, A와 B가 친구라는 뜻www.acmicpc.net 🔺 코드1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162import java.util.*;import java.io.*; public class Main { static int N, M; static int INF = 10000001; ..
![]()
🔺 문제 11403번: 경로 찾기 가중치 없는 방향 그래프 G가 주어졌을 때, 모든 정점 (i, j)에 대해서, i에서 j로 가는 경로가 있는지 없는지 구하는 프로그램을 작성하시오. www.acmicpc.net 🔺 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 import java.util.*; import java.io.*; public class Main { static int N; static int[][] distance; public static void main(String[] args) throws IOException { BufferedRe..
![]()
🔺 문제 11404번: 플로이드첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가www.acmicpc.net 🔺 코드123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354import java.util.*;import java.io.*; public class Main { static int N, M; static int[][] distance; // 최단 거리 배열 - 인접 행렬 static int max = 1000000..
