백준 1719 택배 자바

🔗 백준 1719 택배 

📌오늘의 학습 키워드

• 문제에서 나 플루이드 워셜 이에요~~ 라고 티를 내고 있다.
• 하지만 특이한 게 있다면 첫번째로 들러야 하는 지점을 저장해야한다는 것!

✨공부한 내용 본인의 언어로 정리하기

• 단순히 "이동 가능한 가장 짧은 거리를 구하시오" 했으면 쉬웠을 것이다.
• 첫번째로 들러야 하는 지점을 찾기 위해 업데이트 하면서 DP로 어디를 지나왔는 지 추적해야했다.

📚오늘의 회고

• 첫번째 지점을 찾기 위해 지나온 점을 계속 추적해 나가는 방법을 사용했다. 
• 테스트시 사용했던 코드는 꼭 지우자^^

[🤓문제 해결 코드]

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class Main {
	static int N, M, a, b, c;
	static int[][] arr, ans, edges;
	
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		StringBuilder sb = new StringBuilder();
		
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		
		arr = new int[N+1][N+1];
		ans = new int[N+1][N+1];
		edges = new int[N+1][N+1];
		
		for(int i=0; i<=N; i++) {
			for(int j=0; j<=N; j++) {
				arr[i][j] = 100001;
				ans[i][j] = 2000;
			}
			arr[i][i] = 0;
		}
		
		for(int i=0; i<M; i++) {
			st = new StringTokenizer(br.readLine());
			
			a = Integer.parseInt(st.nextToken());
			b = Integer.parseInt(st.nextToken());
			c = Integer.parseInt(st.nextToken());
			
			arr[a][b] = c;
			arr[b][a] = c;
			ans[a][b] = b;
			ans[b][a] = a;
			edges[a][b] = 1;
			edges[b][a] = 1;
		}
		
		for(int k=1; k<=N; k++) {
			for (int i=1; i<=N; i++) {
				for (int j=1; j<=N; j++) {
					if(arr[i][j] > arr[i][k] + arr[k][j]) {
						arr[i][j] = arr[i][k] + arr[k][j];
						int t = k;
						while(i != t) {
							if(ans[i][t] == t) {
								ans[i][j] = t;
								break;
							}
							t = ans[i][t];
						}
					}
				}
			}
		}
		
		for (int i=1; i<=N; i++) {
			for (int j=1; j<=N; j++) {
				if(i==j)
					sb.append("- " );
				else
					sb.append(ans[i][j]).append(" ");
			}
			sb.append("\n");
		}
		
		System.out.println(sb);
		
	}
}