들어가며
플로이드 워셜(Floyd-Warshall) 알고리즘은 모든 정점 쌍 사이의 최단 거리를 구하는 알고리즘입니다. 3중 for문을 사용해서 전체 경로에 대해 지나칠 수 있는 노드를 점차 확장하며 가장 적은 비용의 경로를 찾아냅니다. 1번 노드 혹은 마지막 노드부터 순차적으로 확장하는 다이나믹 프로그래밍의 일종입니다.
플로이드 워셜 알고리즘은 구현은 쉽지만 처음 접한다면 어려울 수 있으므로 그래프, 인접 행렬, DP(Bottom Up의 Tabulatoin)의 개념을 미리 숙지하고 보면 더 좋습니다.
Floyd-Warshall 알고리즘
1. 개요
플로이드 워셜 알고리즘은 1962년 로버트 플로이드가 현재 사용되는 형태로 발표한 알고리즘으로 플로이드 알고리즘, 로이-워셜 알고리즘 등의 이름으로도 불립니다.
플로이드 워셜 알고리즘은 그래프에 방향이 존재하는 경우엔 음의 가중치가 있어도 사용할 수 있지만, 음의 사이클이 존재하면 사용할 수 없습니다. 또한, 무방향 가중치 그래프의 경우엔 음의 가중치도 존재하면 안 됩니다. 이는 포스트의 후반부에서 자세히 다루겠습니다.
2. 알고리즘의 동작
우선 말로 알고리즘의 동작을 간단히 짚고 넘어가보겠습니다.
이 알고리즘은 가중치가 있는 그래프에서 모든 쌍에 대해 최소 비용을 탐색합니다. 이때, 직접(Direct) 가는 것이 나은지 다른 노드를 거쳐가는(Via) 것이 나은지 비교하며 순차적으로 비용을 업데이트합니다.
처음 인접 행렬에는 다이렉트로 가는 비용만 저장되어있고, 우선 첫번째 노드를 거쳐가는 경우에 대한 계산이 이루어집니다. 1번 노드를 거쳐가는 것이 더 나은 경우 인접 행렬에서 해당 비용으로 값이 갱신됩니다. 첫번째 노드를 거쳐가는 경우에 대한 갱신이 끝나면 2번 노드를 거쳐가는 경우에 대한 탐색이 이루어집니다. 이때 인접 행렬에는 이미 1번 노드를 거쳐가는 경우에 대한 최적화가 끝났기 때문에 두번째에는 단순히 2번 노드를 거쳐가는 것이 나은지, 직접 가는게 나은지 비교하는 것이 아닙니다. (자세한 설명은 아래에서 하겠습니다.) 이렇게 n번 노드까지 거쳐가는 경우를 전부 확인하면 최종 인접 행렬엔 모든 이동에 대한 최소 비용이 저장되어있습니다.
이렇게 반복문으로 작은 문제부터 값을 구하며 확장하는 것은 다이나믹 프로그래밍의 Bottom Up 방식인 Tabulation에 해당합니다.
경유하는 노드의 순서를 임의로 지정할 수 없을까?
3. 시간복잡도
앞서 언급했듯이 3중 for문으로 구현하는 알고리즘이므로 노드 개수 n의 그래프에 대해 O(N^3)의 시간복잡도를 가집니다.
인접 행렬(Adjacency Matrix)
인접 행렬이란 위의 표와 같이 그래프에서 각 정점이 어느 정점과 연결되었는지 보여주는 정사각형 행렬입니다. 간선에 가중치가 존재하지 않는다면 1과 0으로 나타낼 수 있지만, 가중치가 존재한다면 행렬의 각 값은 비용(cost)으로 저장됩니다.
위처럼 그래프가 주어진 경우 인접 행렬은 아래와 같이 나타낼 수 있습니다. (위의 그래프로 플로이드 워셜 알고리즘 설명까지 진행합니다.)
| start(i) \ end(j) | 1 | 2 | 3 | 4 | 5 | 6 |
| 1 | 0 | ∞ | 3 | 5 | 10 | ∞ |
| 2 | ∞ | 0 | 7 | 3 | 5 | ∞ |
| 3 | 3 | 7 | 0 | 1 | ∞ | ∞ |
| 4 | 5 | 3 | 1 | 0 | ∞ | 3 |
| 5 | 10 | 5 | ∞ | ∞ | 0 | 3 |
| 6 | ∞ | ∞ | ∞ | 3 | 3 | 0 |
처음 인접 행렬은 직접 이동할 수 있는 경우에만 비용이 저장되어있습니다.
위의 인접 행렬을 adj로 선언한 경우 adj[i][j]의 의미는 i에서 j로 이동할 때의 비용입니다. 비용이 ∞인 경우는 직접적으로 연결된 간선이 존재하지 않음을 뜻합니다. 또한 i와 j가 같은 경우는 출발 노드와 도착 노드가 같다는 뜻으로 비용이 항상 0입니다.
i에서 j로 이동할 때 특정 노드 k를 거쳐간다면 비용 newCost는 adj[i][k] + adj[k][j]가 될 것입니다.
플로이드 워셜 알고리즘 동작
1. 인접 행렬 최초 저장
| start(i) \ end(j) | 1 | 2 | 3 | 4 | 5 | 6 |
| 1 | 0 | ∞ | 3 | 5 | 10 | ∞ |
| 2 | ∞ | 0 | 7 | 3 | 5 | ∞ |
| 3 | 3 | 7 | 0 | 1 | ∞ | ∞ |
| 4 | 5 | 3 | 1 | 0 | ∞ | 3 |
| 5 | 10 | 5 | ∞ | ∞ | 0 | 3 |
| 6 | ∞ | ∞ | ∞ | 3 | 3 | 0 |
앞에서 봤던 인접 행렬처럼 최초에는 노드에서 다른 노드로 직접 이동하는 비용만 저장되고 나머지는 모두 ∞로 저장됩니다.
2. 1번 노드를 경유하는 탐색( k = 1 )
이제부턴 노드 i에서 j로 이동할 때 1번 노드를 경유하는 것과 다이렉트로 이동하는 것 중 최소 비용을 구합니다. 모든 (i, j) 쌍에 대해 k를 경유하는 경우를 확인하며 갱신합니다.
i) i = 1, j = 1
1에서 1을 거쳐 1로 가는 경우는 항상 비용이 0입니다.
ii) i = 1, j = 2~6
또한, 1에서 1을 거쳐 노드 2~6으로 도착하는 것은 거쳐가는 의미가 없기 때문에 변화없이 다음 단계로 넘어갑니다.
iii) i = 2, j = 1~2
위와 같은 이유로 스킵합니다.
iv) i = 2, j = 3~6
2번 노드에서 출발해 1번 노드를 거쳐 3~6번 노드로 가는 경우입니다. 여전히 불가능하기 때문에 스킵합니다. 나중에 보겠지만 실제 코드에선 2번 노드에서 1번 노드로 가는 비용에 해당하는 무한대와 1번 노드에서 3~6번 노드로 가는 비용의 합을 adj[2][3]과 비교합니다.
v) i = 3, j = 1~3
ii와 같은 이유로 스킵합니다.
vi) i = 3, j = 4
기존의 인접 행렬에 저장된 adj[3][4]의 값은 1입니다. 그리고 1번 노드를 거쳐가는 경우 비용은 3+5=8입니다. 3번 노드에서 4번 노드로 갈 땐 1번 노드를 경유하지 않는 것이 유리한 것을 알 수 있습니다.
vii) i = 3, j = 5
3번 노드에서 5번 노드로 직접 연결된 간선이 존재하지 않습니다. 따라서 adj[3][5]는 무한대입니다. 하지만 1번 노드를 거쳐가는 경우엔 3+10=13의 비용으로 이동할 수 있습니다.
따라서 adj[3][5] = 13으로 갱신됩니다.
viii) i = 3, j = 6
3번 노드에서 6번 노드로 직접 연결된 간선도 존재하지 않고, 1번 노드를 직접 거쳐서 이동하는것도 불가능합니다. 따라서 adj[3][6]의 값은 바뀌지 않습니다.
ix) i = 4, j = 1~4
앞선 여러 상황들과 같기 때문에 스킵 가능합니다.
x) i = 4, j = 5
4번 노드에서 5번 노드로 직접 연결된 간선은 없지만, 1번 노드를 거치는 경우 15의 비용으로 갈 수 있습니다.
따라서 adj[4][5] = 15로 갱신됩니다.
xi) i = 4, j = 6 그리고 i = 5, j = 1~2
앞선 여러 상황들과 같기 때문에 스킵 가능합니다.
xii) i = 5, j = 3~4
3~4번 노드에서 5번 노드로의 비용을 구했던 것과 동일합니다.
xiii) i = 5, j = 5~6
생략 가능합니다.
xiv) i = 6, j = 1~6
6번 노드는 1번 노드로의 직접적인 경로가 없으므로 모두 생략 가능합니다.
k = 1일 때, 인접 행렬을 갱신한 결과는 아래와 같습니다. 빨간색 숫자가 이번에 갱신된 최소 비용입니다.
| start(i) \ end(j) | 1 | 2 | 3 | 4 | 5 | 6 |
| 1 | 0 | ∞ | 3 | 5 | 10 | ∞ |
| 2 | ∞ | 0 | 7 | 3 | 5 | ∞ |
| 3 | 3 | 7 | 0 | 1 | 13 | ∞ |
| 4 | 5 | 3 | 1 | 0 | 15 | 3 |
| 5 | 10 | 5 | 13 | 15 | 0 | 3 |
| 6 | ∞ | ∞ | ∞ | 3 | 3 | 0 |
3. 2번 노드를 경유하는 Case 탐색 ( k = 2 )
1번 노드를 거쳐가는 케이스에 대해서 모든 경우에 대하여 자세하게 설명했기 때문에 이제부턴 중요한 부분만 짚으면서 넘어가겠습니다.
i) i = 3, j = 4
3번 노드에서 2번 노드를 거쳐 4번 노드를 가는 경우 직접 경로 1과 7+3=10의 비교이므로 갱신이 일어나지 않습니다.
무방향 그래프이므로 4번 노드에서 출발해 2번 노드를 거쳐 3번 노드로 향하는 경우도 동일합니다. 앞으로 대칭이 되는 경우에 대해서는 생략하겠습니다.
ii) i = 3, j = 5
3번 노드와 5번 노드를 직접 잇는 간선은 없습니다. 하지만 1번 노드를 거쳐가면서 13이라는 비용으로 이동할 수 있게 되었습니다. 그런데 지금처럼 2번 노드를 거쳐간다면 7+5=12의 비용으로 이동할 수 있습니다.
따라서 adj[3][5] = 12로 갱신됩니다.
iii) i = 4, j = 5
앞선 경우처럼 4번 노드와 5번 노드를 직접 잇는 간선은 없지만 1번 노드를 거쳐가며 15라는 비용으로 이동할 수 있습니다.
그런데 지금처럼 2번 노드를 거쳐간다면 3+5=8의 비용으로 이동할 수 있게 됩니다.
따라서 adj[4][5] = 8로 갱신됩니다.
k = 2일 때, 인접 행렬을 갱신한 결과는 아래와 같습니다. 빨간색 숫자가 이번에 갱신된 최소 비용입니다.
| start(i) \ end(j) | 1 | 2 | 3 | 4 | 5 | 6 |
| 1 | 0 | ∞ | 3 | 5 | 10 | ∞ |
| 2 | ∞ | 0 | 7 | 3 | 5 | ∞ |
| 3 | 3 | 7 | 0 | 1 | 12 | ∞ |
| 4 | 5 | 3 | 1 | 0 | 8 | 3 |
| 5 | 10 | 5 | 12 | 8 | 0 | 3 |
| 6 | ∞ | ∞ | ∞ | 3 | 3 | 0 |
4. 3번 노드를 경유하는 Case 탐색 ( k = 3 )
이제 3번 노드를 거쳐가는 경우입니다.
i) i = 1, j = 2
1번 노드에서 2번 노드로 가는 비용은 무한대이지만 3번 노드를 거치는 경우 3+7=10의 비용으로 이동할 수 있습니다.
따라서 adj[1][2] = 10으로 갱신됩니다.
ii) i = 1, j = 4
1번 노드에서 4번 노드로 직접 가는 비용은 5이지만, 3번 노드를 거치는 경우 3+1=4의 비용으로 이동할 수 있습니다.
따라서 adj[1][4] = 4로 갱신됩니다.
k = 3일 때, 인접 행렬을 갱신한 결과는 아래와 같습니다. 빨간색 숫자가 이번에 갱신된 최소 비용입니다.
| start(i) \ end(j) | 1 | 2 | 3 | 4 | 5 | 6 |
| 1 | 0 | 10 | 3 | 4 | 10 | ∞ |
| 2 | 10 | 0 | 7 | 3 | 5 | ∞ |
| 3 | 3 | 7 | 0 | 1 | 12 | ∞ |
| 4 | 4 | 3 | 1 | 0 | 8 | 3 |
| 5 | 10 | 5 | 12 | 8 | 0 | 3 |
| 6 | ∞ | ∞ | ∞ | 3 | 3 | 0 |
5. 4번 노드를 경유하는 Case 탐색 ( k = 4 )
이제 4번 노드를 거쳐가는 경우에 대해 모든 (i, j) 쌍을 갱신합니다.
i) i = 1, j = 2
1번 노드에서 4번 노드를 거쳐서 2번 노드로 가는 경우입니다. 앞에서 1번 노드에서 4번 노드로 가는 최소 비용은 5가 아니라 4라는 것을 알았기 때문에 4번 노드를 거쳐가는 비용은 4+3=7입니다. 또한, 1번 노드에서 3번 노드를 거쳐 2번 노드로 가는 최소 비용은 10이었습니다.
따라서 adj[1][2] = 7로 갱신됩니다.
1번 노드에서 2번 노드로 향하는 경로는 1 > 3 > 4임에 주의해야 한다.
1번 노드에서 단순히 4번 노드를 거쳐서 2번 노드로 가는 비용과 기존의 비용을 비교했지만 1번 노드에서 4번 노드로 이동하는 비용은 앞에서 1번 > 3번 > 4번에 의한 결과임을 알아야합니다.
ii) i = 1, j = 6
i의 경우와 마찬가지로 1번 노드에서 4번 노드를 거쳐서 6번 노드로 이동하는 최소 비용은 4+3=7입니다.
ii) i = 2, j = 3
2번 노드에서 4번 노드를 거쳐 3번 노드로 이동하는 경우 3+1=4가 최소 비용임을 알 수 있습니다.
iii) i = 2, j = 6
2번 노드에서 4번 노드를 거쳐 6번 노드로 이동하는 경우 3+3=6이 최소 비용임을 알 수 있습니다.
iv) i = 3, j = 5
이 경우는 adj[3][4] + adj[4][5]를 구해서 최소 비용을 갱신해야합니다. adj[3][4] = 1이고, adj[4][5] = 8입니다. 1+8=9는 기존의 비용 12보다 작기 때문에 adj[3][5] = 9로 갱신됩니다.
이 또한 3번 노드에서 5번 노드로 향하는 경로는 3 > 4 > 2 > 5임에 주의해야 한다.
4번 노드에서 5번 노드로의 최소 비용은 2번 노드를 거쳐간 경우에 대한 최소 비용이므로 경로는 3 > 4 > 2 > 5입니다.
v) i = 3, j = 6
3번 노드에서 4번 노드를 거쳐 6번 노드로 가는 경우는 1+3=4가 최소 비용임을 알 수 있습니다.
k = 4일 때, 인접 행렬을 갱신한 결과는 아래와 같습니다. 빨간색 숫자가 이번에 갱신된 최소 비용입니다.
| start(i) \ end(j) | 1 | 2 | 3 | 4 | 5 | 6 |
| 1 | 0 | 7 | 3 | 4 | 10 | 7 |
| 2 | 7 | 0 | 4 | 3 | 5 | 6 |
| 3 | 3 | 4 | 0 | 1 | 9 | 4 |
| 4 | 4 | 3 | 1 | 0 | 8 | 3 |
| 5 | 10 | 5 | 9 | 8 | 0 | 3 |
| 6 | 7 | 6 | 4 | 3 | 3 | 0 |
6. 5번 노드를 경유하는 Case 탐색 ( k = 5 )
이제 5번 노드를 거쳐가는 경우에 대해 모든 (i, j) 쌍을 갱신해야합니다. 하지만 5번 노드를 경유하는 경우엔 최소 비용이 갱신되지 않습니다.
7. 6번 노드를 경유하는 Case 탐색 ( k = 6 )
이제 7번 노드를 거쳐가는 경우에 대해 모든 (i, j) 쌍을 갱신합니다.
i) i = 3, j = 5
3번 노드에서 6번 노드를 거쳐 5번 노드로 가는 경우 adj[3][6]과 adj[6][5]의 합으로 최소 비용을 갱신할 수 있습니다. 앞에서 강조했던 것처럼 3번 노드에서 6번 노드로 이동하는 것은 4번 노드를 경유할 때 최소 비용이 발생하므로 4+3=7의 비용이 발생하는 것을 알 수 있습니다.
기존의 비용인 9보다 작으므로 adj[3][5] = 7로 갱신됩니다.
ii) i = 4, j = 5
4번 노드에서 6번 노드를 거쳐 5번 노드로 가는 경우 i의 경우와 동일한 방법으로 최소 비용이 6임을 알 수 있습니다.
k = 6일 때, 인접 행렬을 갱신한 결과는 아래와 같습니다. 빨간색 숫자가 이번에 갱신된 최소 비용입니다.
| start(i) \ end(j) | 1 | 2 | 3 | 4 | 5 | 6 |
| 1 | 0 | 7 | 3 | 4 | 10 | 7 |
| 2 | 7 | 0 | 4 | 3 | 5 | 6 |
| 3 | 3 | 4 | 0 | 1 | 7 | 4 |
| 4 | 4 | 3 | 1 | 0 | 6 | 3 |
| 5 | 10 | 5 | 7 | 6 | 0 | 3 |
| 6 | 7 | 6 | 4 | 3 | 3 | 0 |
위의 인접 행렬이 그래프의 최소 비용을 구한 최종 결과입니다.
플로이드 워셜 알고리즘 구현 코드
1. 전체 코드
인접 행렬이 직접 주어질 수도 있고, 간선 정보를 바탕으로 인접 행렬을 만들어야할 수도 있습니다. 아래는 간선 정보를 바탕으로 인접 행렬을 만든 뒤에 최소 비용을 구하는 코드입니다. 코드에 대한 설명은 아래에 있습니다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int node = Integer.parseInt(br.readLine());
int m = Integer.parseInt(br.readLine());
int [][]adj = new int[node+1][node+1];
for(int i = 0; i <= node; i++) {
Arrays.fill(adj[i], 100_000_000);
adj[i][i] = 0;
}
StringTokenizer st;
for(int i = 0; i < m; i++) {
st = new StringTokenizer(br.readLine(), " ");
int start = Integer.parseInt(st.nextToken());
int end = Integer.parseInt(st.nextToken());
int cost = Integer.parseInt(st.nextToken());
adj[start][end] = cost;
adj[end][start] = cost;
}
for(int k = 1; k <= node; k++) {
for(int i = 1; i <= node; i++) {
for(int j = 1; j <= node; j++) {
adj[i][j] = Math.min(adj[i][j], adj[i][k] + adj[k][j]);
}
}
}
StringBuilder sb = new StringBuilder();
for(int i = 1; i <= node; i++) {
for(int j = 1; j <= node; j++) {
if(i == j) sb.append("\\ ");
else sb.append(adj[i][j]+" ");
}
sb.deleteCharAt(sb.length()-1).append("\n");
}
System.out.println(sb.toString().trim());
}
}입력
6
9
1 3 3
1 4 5
1 5 10
2 3 7
2 4 3
2 5 5
3 4 1
4 6 3
5 6 3
출력
\ 7 3 4 10 7
7 \ 4 3 5 6
3 4 \ 1 7 4
4 3 1 \ 6 3
10 5 7 6 \ 3
7 6 4 3 3 \
변수의 의미는 다음과 같습니다.
- node : 그래프 상에 존재하는 노드의 개수
- m : 입력에서 주어지는 간선 정보의 개수
- adj 배열 : 노드 i에서 j로 이동할 때의 최소 비용을 저장하는 배열
2. 인접 행렬 생성
int node = Integer.parseInt(br.readLine());
int m = Integer.parseInt(br.readLine());
int [][]adj = new int[node+1][node+1];
for(int i = 0; i <= node; i++) {
Arrays.fill(adj[i], 100_000_000);
adj[i][i] = 0;
}
StringTokenizer st;
for(int i = 0; i < m; i++) {
st = new StringTokenizer(br.readLine(), " ");
int start = Integer.parseInt(st.nextToken());
int end = Integer.parseInt(st.nextToken());
int cost = Integer.parseInt(st.nextToken());
adj[start][end] = cost;
adj[end][start] = cost;
}
다음과 같은 순서로 인접 행렬을 만들었습니다.
- 인접 행렬을 node+1로 한 이유는 그래프의 노드가 1부터 시작하도록 정의되어 있기 때문입니다.
- 처음엔 노드와 노드 사이의 최소 비용을 알 수 없기 때문에 전부 최대값으로 할당합니다. 주대각선은 항상 최소 비용이 0입니다.
- 무방향 가중치 그래프이므로 인접 행렬의 양방향으로 비용을 저장합니다.
직접적인 경로가 없는 경우 Integer.MAX_VALUE가 아닌 10^7을 사용하는 이유
i 노드에서 j 노드로 이동할 때 k 노드를 거쳐가는 경우로 예시를 들겠습니다. i 노드에서 k 노드로 이동했다가 k 노드에서 j 노드로 이동한다면 그 비용은 adj[i][k] + adj[k][j] 입니다. 그런데 i에서 k 노드로 직접 연결된 간선이 없을 때 해당 비용을 Integer.MAX_VALUE로 저장했다면 adj[k][j] 값과 덧셈을 할 때 정수 오버플로우가 발생합니다. 따라서 무한대의 값을 1억 정도의 값으로 여유를 둬서 저장합니다.
3. k번 노드를 경유하며 최소 비용을 점진적으로 갱신
for(int k = 1; k <= node; k++) {
for(int i = 1; i <= node; i++) {
for(int j = 1; j <= node; j++) {
adj[i][j] = Math.min(adj[i][j], adj[i][k] + adj[k][j]);
}
}
}
핵심 알고리즘인 최소 비용 갱신 구현은 정말 단순합니다. 3중 for문에서 제일 바깥에 경유할 노드를 지정합니다. 그리고 k를 순차적으로 증가시키면서 모든 (i, j) 쌍에 대해서 k 노드를 경유하는 것이 나은지 기존이 나은지를 판단합니다.
4. 최종 인접 행렬 출력
StringBuilder sb = new StringBuilder();
for(int i = 1; i <= node; i++) {
for(int j = 1; j <= node; j++) {
if(i == j) sb.append("\\ ");
else sb.append(adj[i][j]+" ");
}
sb.deleteCharAt(sb.length()-1).append("\n");
}
System.out.println(sb.toString().trim());
I/O 성능을 고려해 StringBuilder를 이용해서 한 번에 출력합니다.
플로이드 워셜 알고리즘을 적용할 수 없는 그래프
1. 무방향 그래프 내에 음의 가중치가 존재하는 경우
처음 플로이드 워셜 알고리즘의 개요를 작성하면서 무방향 그래프에서 음의 가중치는 불가능하다고 했습니다. 그 이유를 실제 예를 들어서 확인해보겠습니다.
3번 노드에서 4번 노드로 이동하는 경우를 보겠습니다. 가중치가 음수라서 최소 비용은 -15입니다. 하지만 여기서 끝나는 것이 아니라 다시 3번 노드로 돌아갔다가 4번 노드로 이동한다면 최소 비용은 -15*3=-45가 됩니다. 즉, 음의 가중치를 가진 간선을 왕복할 때마다 최소 비용이 한없이 작아지므로 무방향 그래프에서 음의 가중치는 존재할 수 없습니다.
2. 단방향 그래프에서 음의 사이클이 존재하는 경우
다음으로 방향이 존재하는 그래프에서 음의 사이클이 존재하는 경우를 보겠습니다.
4번 노드에서 3번 노드로 이동할 때의 최소 비용은 -15입니다. 하지만 4번 → 3번 → 1번 → 4번을 거쳐서 다시 3번 노드로 이동한다면 최소 비용은 -15+3+7-15=-20으로 음의 사이클을 돌때마다 최소 비용이 낮아집니다. 따라서 음의 사이클을 가진 경우에도 최소 비요이 한없이 작아지므로 단방향 그래프에서 음의 사이클은 존재할 수 없습니다.
.
.
.
마치며
처음으로 그래프에 관한 알고리즘을 다루게 되었습니다. 그래프 문제가 제일 재밌어서 다른 것보다 가장 시간을 많이 투자해서 공부했더니 레이팅 1등이네요! 기본적인 DFS와 BFS 개념부터 다루고 싶었는데 플로이드 워셜 알고리즘을 계속 미루다가 이제서야 확실히 정리해서 이것부터 작성하게 되었습니다ㅎㅎ 앞으로 열심히 공부했던 그래프 관련 알고리즘도 얼른 정리해서 쓰겠습니다!
아래는 플로이드 워셜 알고리즘 연습하기 좋은 기초 문제들입니다.
- 11403 경로 찾기 : https://www.acmicpc.net/problem/11403
- 11404 플로이드 : https://www.acmicpc.net/problem/11404
- 10159 저울 : https://www.acmicpc.net/problem/10159
그럼 궁금한 점이나 피드백은 댓글로 부탁드립니다!
'Algorithm' 카테고리의 다른 글
| [Algorithm] BFS 알고리즘 with JAVA (0) | 2025.05.09 |
|---|---|
| [Algorithm] 그래프 이론 및 그래프 탐색 (0) | 2025.05.09 |
| [Algorithm] Z 알고리즘 with JAVA (1) | 2025.02.21 |
| [Algorithm] 분할 정복을 이용한 행렬의 거듭제곱으로 Fibonacci 수열 구하기 with JAVA (0) | 2025.01.07 |
| [Algorithm] CCW 알고리즘 with JAVA (1) | 2024.12.17 |