백준(Java)/23년 8월
[Java] 백준 - 11404번: 플로이드
C0MPAS
2023. 8. 31. 23:19
9월 1일(금) - 그래프와 순회 (11404번)
11404번: 플로이드
첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가
www.acmicpc.net
ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ
문제점
ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ
풀이
(C언어 풀이 활용)
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
static final int INF = 987654321;
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
int N = Integer.parseInt(br.readLine());
int M = Integer.parseInt(br.readLine());
int[][] arr = new int[N+1][N+1];
for(int i=1; i<=N; i++)
{
for(int j=1; j<=N; j++)
{
arr[i][j] = INF;
if(i == j)
{
arr[i][j] = 0;
}
}
}
for(int i=0; i<M; i++)
{
st = new StringTokenizer(br.readLine());
int a = Integer.parseInt(st.nextToken());
int b = Integer.parseInt(st.nextToken());
int c = Integer.parseInt(st.nextToken());
arr[a][b] = Math.min(arr[a][b], c);
}
for (int i = 1; i <= N; i++)
{
for (int j = 1; j <= N; j++)
{
for (int k = 1; k <= N; k++)
{
if (arr[j][i] != INF && arr[i][k] != INF)
{
arr[j][k] = Math.min(arr[j][k], arr[j][i] + arr[i][k]);
}
}
}
}
StringBuilder sb = new StringBuilder();
for(int i=1; i<=N; i++)
{
for(int j=1; j<=N; j++)
{
int result = (arr[i][j] != INF) ? arr[i][j] : 0;
sb.append(result).append(" ");
}
sb.append("\n");
}
System.out.println(sb);
}
}ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ