1. ๊ฐ๋ ๐๐ฆบ
ํ๋ก์ด๋-์์ฌ(Floyd-Warshall) ์๊ณ ๋ฆฌ์ฆ์ด๋ ๋ชจ๋ ์ ์ ์์ ๋ค๋ฅธ ๋ชจ๋ ์ ์ ๊น์ง์ ์ต๋จ ๊ฒฝ๋ก๋ฅผ ๊ตฌํ๋ ์๊ณ ๋ฆฌ์ฆ์ด๋ค. ๋ค์ต์คํธ๋ผ(Dijkstra) ์๊ณ ๋ฆฌ์ฆ๊ณผ ๋ค๋ฅด๊ฒ ์์ ๊ฐ์ค์น๋ฅผ ํ์ฉํ๋ค๋ ๊ฒ ํน์ง์ด๋ผ๊ณ ํ ์ ์๋ค.
๋ค์ต์คํธ๋ผ ์๊ณ ๋ฆฌ์ฆ์ ๊ฐ๋จํ๊ฒ ์ค๋ช ํ์๋ฉด ์ถ๋ฐ ์ ์ ์ผ๋ก๋ถํฐ ๋ชจ๋ ์ ์ ๊น์ง์ ์ต๋จ๊ฒฝ๋ก๋ฅผ ๊ตฌํ๋ ์๊ณ ๋ฆฌ์ฆ์ด๋ค. ๋ค์ต์คํธ๋ผ๋ฅผ ์ด์ฉํ์ฌ ํ๋ก์ด๋-์์ฌ ์๊ณ ๋ฆฌ์ฆ์ ๊ตฌํํ๋ค๊ณ ํ๋ฉด ์ถ๋ฐ ์ ์ ์ ๋ชจ๋ ์ ์ ์ ๊ฐ์๋งํผ ์ค์ ํด ์ฃผ๋ฉด ๋๋ค.
์์ฐจ ํ์ ๋ฐฉ๋ฒ์ผ๋ก ๋ค์ต์คํธ๋ผ๋ฅผ ๊ตฌํํ๋ฉด O(V^2)์ด๊ณ , ๋ชจ๋ ์ ์ ์ ์ถ๋ฐ ์ ์ ์ผ๋ก ํ๋ค๊ณ ํ๋ฉด O(V * V^2) = O(V^3)์ด ๋๊ฒ ๋๋ค. ํ๋ก์ด๋-์์ฌ ์๊ณ ๋ฆฌ์ฆ์ ์๊ฐ๋ณต์ก๋ ๋ํ O(V^3)์ผ๋ก ๊ฐ๋ค. ํ์ง๋ง ํ๋ก์ด๋-์์ฌ ์๊ณ ๋ฆฌ์ฆ์ ๊ตฌํ์ ๋ค์ต์คํธ๋ผ์ ๋นํด ๋งค์ฐ ๊ฐ๋จํ๋ฏ๋ก ํด๋น ๋ฐฉ๋ฒ์ ์ตํ๋๋๋ก ํ์.
2. ๋์๋ฐฉ์ ๐
ํ๋ก์ด๋-์์ฌ์ DP๋ฅผ ์ด์ฉํ๋ค.
DP[i][j][k]๋ ์ ์ {1, 2,..., k}๋ง์ ๊ฒฝ์ ๊ฐ๋ฅํ ์ ์ ๋ค๋ก ์๊ฐํ๊ณ , ์ ์ i๋ก๋ถํฐ ์ ์ j๊น์ง์ ๋ชจ๋ ๊ฒฝ๋ก ์ค ๊ฐ์ฅ ์งง์ ๊ฒฝ๋ก์ ๊ฑฐ๋ฆฌ์ด๋ค. ์ด๋, {1, 2,..., k}์ ์ํ ๋ชจ๋ ์ ์ ๋ค์ ๋ฐ๋์ ๊ฒฝ์ ํ๋ ๊ฒ ์๋๋ผ ๊ฒฝ์ ๋ฅผ ํ ์๋ ์๊ณ ์ ํ ์๋ ์๋ค๋ ๊ฒ์ ์ฃผ์ํ์.
๊ทธ๋ฌ๋ฉด DP[i][j][k]์ ์ด๋ป๊ฒ ํํํ ์ ์์๊น? DP[i][j][k] = min(DP[i][j][k-1], DP[i][k][k-1] + DP[k][j][k-1])๋ผ๊ณ ํ ์ ์๋ค.
- DP[i][j][k-1] : ์์ k๋ฅผ ๊ณ ๋ คํ์ง ์๊ณ {1, 2,..., k-1}์ ์์๋ง ๊ณ ๋ คํ ๊ฒฝ์ฐ
- DP[i][k][k-1] + DP[k][j][k-1] : {1, 2,..., k-1}์ ์์๋ฅผ ๊ณ ๋ คํ์์ง๋ง k๋ฅผ ๊ฒฝ์ ํ๊ธฐ ๋๋ฌธ์ ๊ฒฐ๊ตญ {1, 2,..., k}๋ฅผ ๊ณ ๋ คํ๋ ๊ฒฝ์ฐ
์ฆ, DP[i][j][k]๋ '{1, 2,..., k-1}๋ง ๊ณ ๋ คํ ๊ฒฝ์ฐ'์ 'k๋ฅผ ๋ฌด์กฐ๊ฑด ํฌํจํ๊ณ {1, 2,..., k}๋ฅผ ๊ณ ๋ คํ๋ ๊ฒฝ์ฐ' ์ค์ ์ต๋จ ๊ฒฝ๋ก๋ฅผ ์ ํํ๋ ๊ฒ์ด๋ค. (DP์ ์๋ฆฌ๋ฅผ ์๊ณ ์๋ค๋ฉด ์ฝ๊ฒ ์ดํดํ ์ ์์ ๊ฒ์ด๋ค.)
์ด๋ฅผ ์ฝ๋๋ก ๊ฐ๋จํ๊ฒ ํํํ๋ฉด ์๋์ ๊ฐ๋ค.
V ← Vertext
for k ← 1 to n
for i ← 1 to n (i != k)
for j ← 1 to n ( j != k , j != i)
DP[i][j] = min(DP[i][j], DP[i][k] + DP[k][j]);
3์ฐจ์ ๋ฐฐ์ด๋ก ์๊ฐํ์ง๋ง 2์ฐจ์์ผ๋ก ํํํ ์ ์์๋ ์ด์ ๋ ๋ฌด์์ผ๊น? ๋ฐ๋ก k๊ฐ ๋ฐ๋ณต๋ฌธ์ ๋๊ธฐ ๋๋ฌธ์ด๋ค. DP[i][j] = Math.min(DP[i][j], DP[i][k] + DP[k][j])์์ ์ขํญ์ {1, 2,..., k}๊น์ง ๊ณ ๋ คํ DP์ด๊ณ ์ฐํญ์ {1, 2,..., k-1}๊น์ง ๊ณ ๋ คํ DP์ด๋ค. 'k๊ฐ ์ค๋ฆ์ฐจ์์ผ๋ก ๋ฐ๋ณต๋ฌธ์ ๋๋ ๊ฒ'๊ณผ 'i, j, k๊ฐ ๊ฐ์ ์ํฉ์ ๊ณ ๋ คํ์ง ์๋ ๊ฒ' ๋๋ฌธ์ 3์ฐจ์ ๋ฐฐ์ด์ด ์๋ 2์ฐจ์ ๋ฐฐ์ด๋ง ์ฌ์ฉํด์ ํํํ ์ ์๋ค.
3. ๊ตฌํ(JAVA) ๐ฆฎ
์๊ธฐ ์์ ์ผ๋ก ๊ฐ๋ ๊ฐ์ค์น๋ 0์ผ๋ก ์ค์ ํ๋ค. ๊ทธ๋ฆฌ๊ณ ์ด๊ธฐ ๊ฐ์ ๊ฒฝ์ฐ ๊ฒฝ๋ก๊ฐ ์กด์ฌํ๋ ๊ฒฝ์ฐ์๋ ๊ฒฝ๋ก์ ๊ฐ์ค์น๋ก, ๊ฒฝ๋ก๊ฐ ์กด์ฌํ์ง ์๋๋ค๋ฉด INF(๋ฌดํ๋)๋ก ์ค์ ํ๋ค. ๊ทธ๋์ผ์ง k๊ฐ ์ฆ๊ฐํ๋ฉด์ ๋น๊ตํ ๋ ์ต๋จ ๊ฒฝ๋ก ๊ฐ์ผ๋ก ๋ณ๊ฒฝ์ด ๋๊ธฐ ๋๋ฌธ์ด๋ค. ์ด๋ (INF+INF)๋ฑ์ผ๋ก ์ธํด ์ค๋ฒํ๋ก์ฐ๊ฐ ๋์ง ์๋๋ก ์ฃผ์ํด์ผ ํ๋ค.
[์ ๋ ฅ๋ฐ์ดํฐ]
0 3 8 0 -4
0 0 0 1 7
0 4 0 0 0
2 0 -5 0 0
0 0 0 6 0
static final int INF = 999999;
static int V;
static int[][] DP;
static String[] ss;
public static void main(String[] args) throws IOException {
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
V = 5;
DP = new int[V][V];
for(int i = 0; i < V; i++) {
ss = in.readLine().split(" ");
for(int j = 0; j < V; j++) {
DP[i][j] = Integer.parseInt(ss[j]);
// ๊ฒฝ๋ก๊ฐ ์๋ ๊ฒฝ์ฐ
if((i != j) && (DP[i][j] == 0)) {
DP[i][j] = INF;
}
}
}
for(int k = 0; k < V; k++) {
for(int i = 0; i < V; i++) {
if(i == k)
continue;
for(int j = 0; j < V; j++) {
if((j == k) || (j == i))
continue;
DP[i][j] = Math.min(DP[i][j], DP[i][k] + DP[k][j]);
}
}
}
for(int i = 0; i < V; i++) {
for(int j = 0; j < V; j++) {
System.out.print(DP[i][j] + " ");
}
System.out.println();
}
}
[์ถ๋ ฅ๋ฐ์ดํฐ]
0 1 -3 2 -4
3 0 -4 1 -1
7 4 0 5 3
2 -1 -5 0 -2
8 5 1 6 0
'๐ ์๊ณ ๋ฆฌ์ฆ > ์ต๋จ ๊ฒฝ๋ก' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
๋ค์ต์คํธ๋ผ(Dijkstra) ์๊ณ ๋ฆฌ์ฆ (0) | 2023.03.04 |
---|