[Algorithm /백준] 1240 노드사이의 거리

 

[문제]
 
N개의 노드로 이루어진 트리가 주어지고 M개의 두 노드 쌍을 입력받을 때 두 노드 사이의 거리를 출력하라.

[입력]
첫째 줄에 노드의 개수 
N과 거리를 알고 싶은 노드 쌍의 개수 
M이 입력되고 다음 
N-1개의 줄에 트리 상에 연결된 두 점과 거리를 입력받는다. 그 다음 줄에는 거리를 알고 싶은 
M개의 노드 쌍이 한 줄에 한 쌍씩 입력된다.

[출력]
 M개의 줄에 차례대로 입력받은 두 노드 사이의 거리를 출력한다.

 

[문제 해결 - 플루이드 워셜]

import java.util.Scanner;

public class Main {
	static int [][] arr;
	static boolean []visited;
	static int INF = Integer.MAX_VALUE/4;
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int N = sc.nextInt();
		arr = new int[N+1][N+1];
		visited = new boolean[N+1];
		int M = sc.nextInt();
		for(int i= 0; i < arr.length ; i++) {
			for(int j = 0; j < arr.length ; j++) {
				arr[i][j] = INF;
			}
		}
		for(int i = 1 ; i < N ; i++) {
			int node1 = sc.nextInt();
			int node2 = sc.nextInt();
			int distance = sc.nextInt();
			arr[node1][node2] = distance;
			arr[node2][node1] = distance;
		}
		floyd();
		
		for(int i = 0 ; i < M ;i++) {
			int fstNode = sc.nextInt();
			int secNode = sc.nextInt();
			System.out.println(arr[fstNode][secNode]);
		}
		
	}
	public static void floyd() {
		for(int k = 0 ; k < arr.length ; k++) {
			for(int i =0 ; i < arr.length; i++) {
				for(int j =0; j < arr.length ; j++) {
					if(arr[i][k] >0 && arr[k][j] > 0) {
						arr[i][j] = Math.min(arr[i][j], arr[i][k]+arr[k][j]);
					}
				}
			}
		}
	}
}

 

 

 

+) 원래는 BFS/DFS로 카테고리 분류가 되어있던 문제였으나, 문제를 풀다보니 안풀려서 플로이드 워셜로 풀어버린...

 

하지만 플루이드 워셜의 경우 전체를 다 갱신하기에 숫자가 커지면 시간 초과가 발생할수 있을거 같기도 하다!

 

BFS혹은 DFS로 문제를 다시 풀어볼것