- ๋ชจ๋ ๋ ธ๋์์ ๋ค๋ฅธ ๋ชจ๋ ๋ ธ๋๊น์ง์ ์ต๋จ๊ฒฝ๋ก๋ฅผ ๋ชจ๋ ๊ณ์ฐํจ
- ๋ค์ต์คํธ๋ผ ์๊ณ ๋ฆฌ์ฆ๊ณผ ๋ง์ฐฌ๊ฐ์ง๋ก ๋จ๊ณ๋ณ๋ก ๊ฑฐ์ณ ๊ฐ๋ ๋
ธ๋๋ฅผ ๊ธฐ์ค์ผ๋ก ์๊ณ ๋ฆฌ์ฆ์ ์ํ
- ๋ค์ต์คํธ๋ผ์ ๋ค๋ฅด๊ฒ ๋งค ๋จ๊ณ๋ง๋ค ๋ฐฉ๋ฌธํ์ง ์์ ๋ ธ๋ ์ค์ ์ต๋จ ๊ฑฐ๋ฆฌ๋ฅผ ๊ฐ๋ ๋ ธ๋๋ฅผ ์ฐพ๋ ๊ณผ์ ์ด ํ์ํ์ง ์์.
- 2์ฐจ์ ํ ์ด๋ธ์ ์ต๋จ ๊ฑฐ๋ฆฌ ์ ๋ณด๋ฅผ ์ ์ฅ
- DP ์ ํ์ ์ํจ (์ ํ์์ ๋ง๊ฒ 3์ค FOR๋ฌธ์ ์ด์ฉํด์ 2์ฐจ์ ํ ์ด๋ธ์ ๊ฐฑ์ )
- ๋ ธ๋์ ๊ณ์๊ฐ
- ๋ฐ์ง๊ทธ๋ํ(์์ ๊ทธ๋ํ์ ๊ฐ๊น์ด ๊ทธ๋ํ)์ธ ๊ฒฝ์ฐ ํ๋ก์ด๋ ์์ฌ ์๊ณ ๋ฆฌ์ฆ์ด ํจ์จ์ ์ด๋ค.
- ๋ฐ์ง๊ทธ๋ํ๊ฐ ์๋ ๊ฒฝ์ฐ ๋ค์ต์คํธ๋ผ๋ฅผ n๋ฒ ๋๋ฆฌ๋๊ฒ ๋น ๋ฅด๋ค
O(n^3)
์ ์๊ฐ๋ณต์ก๋๋ก ๋ค์ต์คํธ๋ผ(์ธ์ ํ๋ ฌ์ ์ฌ์ฉํ ๊ฒฝ์ฐ)์ ์๊ฐ๋ณต์ก๋์ ๋์ผํ๋ค- N์ด 100์ด๋ฉด → 100๋ง์ด์ด์ ๊ฐ๋ฅ, 500์ด์ด๋ → 1์ต 2์ฒ 500๋ง ์ด์ด์ tryํด๋ณผ ์ ์๋ค.
- ๊ทธ๋ฌ๋ ํ๋ก์ด๋ ์๊ณ ๋ฆฌ์ฆ์ ๋งค์ฐ ๊ฐ๋จํ์ฌ ๋ค์ต์คํธ๋ผ ์๊ณ ๋ฆฌ์ฆ์ ์ฌ์ฉํ๋ ๊ฒ๋ณด๋ค ํจ์จ์ (์ฝ๋ฉ์ด ํจ์จ์ ์ด๋ผ๋ ๋ป, ์๊ฐ๋ณต์ก๋๊ฐ ํจ์จ์ ์ด๋ผ๋ ๋ป์ด ์๋๋ค!)์ด๋ค
- ์์ ๊ฐ์ค์น๋ ๋๋ค
- ๋ ธ๋์ ๊ฐฏ์๊ฐ ์ ์ ๊ฒฝ์ฐ (500๊ฐ ์ดํ) ์ ์ฌ์ฉํด์ผ ํจ
๐ก์์ ์ฌ์ดํด ๊ฒ์ถ
์๊ธฐ ์์ ์๊ฒ ๊ฐ๋ ๊ฐ์ ๊ฑฐ๋ฆฌ ์ฆ dist[i][i] < 0 ์ด๋ฉด ์์ ์ฌ์ดํด์ ๊ฐ์ง๊ณ ์๋ ๊ฒ
์ ํ์
a์์ b๋ก ๊ฐ๋ ์ต๋จ ๊ฑฐ๋ฆฌ๋ณด๋ค a์์ k๋ฅผ ๊ฑฐ์ณ b๋ก ๊ฐ๋ ๊ฑฐ๋ฆฌ๊ฐ ๋ ์งง์์ง ๊ฒ์ฌ
k์ ๋ชจ๋ ๋ ธ๋, ๋ชจ๋ ๋ ธ๋ a to b → 3์ค ๋ฐ๋ณต๋ฌธ์ด ๋๋ค
์ฝ๋
ํ์ด์ฌ
INF = int(1e9) # ๋ฌดํ์ ์๋ฏธํ๋ ๊ฐ์ผ๋ก 10์ต
n = int(input())
m = int(input())
graph = [[INF] * (n+1) for _ in range(n+1)]
for a in range(1, n+1):
for b in range(1, n+1):
if a==b:
graph[a][b]=0
# ๊ฐ ๊ฐ์ ์ ๋ํ ์ ๋ณด ์
๋ ฅ๋ฐ์, ๊ทธ ๊ฐ์ผ๋ก ์ด๊ธฐํ
for _ in range(m):
# A์์ B๋ก ๊ฐ๋ ๋น์ฉ์ C
a,b,c = map(int,input().split())
graph[a][b] = c
# ํ๋ก์ด๋์์
์๊ณ ๋ฆฌ์ฆ
for k in rangE(1,n+1):
for a in range(1,n+1):
for b in range(1,n+1):
graph[a][b] = min(graph[a][b], graph[a][k] + graph[k][b])
# ์ํ ๊ฒฐ๊ณผ ์ถ๋ ฅ
for a in range(1, n+1):
for b in range(1, n+1):
if graph[a][b]==INF:
print("INFINITY", end=" ")
else:
print(graph[a][b], end= " ")
print()
์๋ฐ
public class Main{
public static final int INF = (int) 1e9; // ๋ฌดํ์ ์๋ฏธํ๋ ๊ฐ์ผ๋ก 10์ต
public static int n,m; // n : ๋
ธ๋์ ๊ฐ์, m : ๊ฐ์ ์ ๊ฐ์
public static int[][] graph = new int[501][501]; // ๋
ธ๋ ๊ฐ์์ ์ต๋๋ 500๊ฐ๋ผ๊ณ ๊ฐ์
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
m = sc.nextInt();
// ์ต๋จ ๊ฑฐ๋ฆฌ ํ
์ด๋ธ์ ๋ชจ๋ ๋ฌดํ์ผ๋ก ์ด๊ธฐํ
for(int i=0;i<501;i++){
Arrays.fill(graph[i],INF);
}
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(i==j){
graph[i][j]=0;
}
}
}
// ๊ฐ ๊ฐ์ ์ ๋ํ ์ ๋ณด ์
๋ ฅ
for(int i=0;i<m;i++){
int a = sc.nextInt();
int b = sc.nextInt();
int c = sc.nextInt();
graph[a][b]=c;
}
// ํ๋ก์ด๋ ์์
์๊ณ ๋ฆฌ์ฆ
for(int k=1;k<=n;k++){
for(int a=1;a<=n;a++){
for(int b=1;b<=n;b++){
graph[a][b] = Math.min(graph[a][b], graph[a][k] + graph[k][b]);
}
}
}
// ๊ฒฐ๊ณผ ์ถ๋ ฅ
for(int a=1; a<=n; a++){
for(int b=1;b<=n;b++){
if(graph[a][b]==INF){
System.out.print("INFINITY ");
}else{
System.out.print(graph[a][b] + " ");
}
}
System.out.println();
}
}
}
'๐ฅ์ฝ๋ฉํ ์คํธ:Algorithm' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
๋ค์ต์คํธ๋ผ (๋ฐฑ์ค 13549 ์จ๋ฐ๊ผญ์ง 3) (1) | 2023.12.26 |
---|---|
ํธ๋ฆฌ์ ์ง๋ฆ (๋ฐฑ์ค 1167๋ฒ) (2) | 2023.12.26 |
๋ฐฑ์ค 9465 ์คํฐ์ปค (2) | 2023.11.29 |
bfs ๋ฐฉ๋ฌธ์ฒดํฌ ์์น (2) | 2023.11.22 |
[swea 1868-ํ์ด์ฌ] ํํํํ ์ง๋ขฐ์ฐพ๊ธฐ (0) | 2023.06.22 |