[백준 - 1240][GOLD 5][해설 X] - 노드사이의 거리 (JAVA)

문제 링크

---

https://www.acmicpc.net/problem/1240

1240번: 노드사이의 거리

 

문제

---

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

 

입력

---

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

출력

---

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

 

제한 

---

•  1≤M≤1,000 
• 2≤N≤1,000 
• 트리 상에 연결된 두 점과 거리는 10,000이하인 자연수이다.
• 트리 노드의 번호는 1부터 N까지 자연수이며, 두 노드가 같은 번호를 갖는 경우는 없다

 

해결 코드

---

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.PriorityQueue;
import java.util.StringTokenizer;


public class Main {	
	public static void main(String[] args) throws Exception {
       BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
       StringTokenizer st = new StringTokenizer(br.readLine());
       int N = Integer.parseInt(st.nextToken());
       int M = Integer.parseInt(st.nextToken());
       	
       int[][] minDistance = new int[N+1][N+1];
       List<Node> graph[] = new ArrayList[N+1];
       
       //그래프와 노드간 거리 초기화
       for(int i=0;i<=N;i++) {
    	   graph[i] = new ArrayList<>();
    	   Arrays.fill(minDistance[i], Integer.MAX_VALUE);
       }
       //그래프 생성
       for(int i=0;i<N-1;i++) {
    	   st = new StringTokenizer(br.readLine());
    	   int start = Integer.parseInt(st.nextToken());
    	   int end = Integer.parseInt(st.nextToken());
    	   int distance = Integer.parseInt(st.nextToken());
    	   
    	   graph[start].add(new Node(end,distance));
    	   graph[end].add(new Node(start,distance));
       }
       
       //다익스트라로 모든 노드와 노드사이의 최단경로 구하기
       for(int start=1;start<=N;start++) {
    	   PriorityQueue<Node> pq = new PriorityQueue<>((x,y)->x.distance - y.distance);
    	   
    	   pq.add(new Node(start,0));
    	   minDistance[start][start] = 0;
    	   
    	   while(!pq.isEmpty()) {
    		   Node curr = pq.poll();
    		  
    		   if(minDistance[start][curr.seq] < curr.distance) {
    			   continue;
    		   }
    		   
    		   for(Node next : graph[curr.seq]) {
    			   if(minDistance[start][next.seq] <= curr.distance + next.distance) {
        			   continue;
        		   }
    			   
    			   minDistance[start][next.seq] = curr.distance + next.distance;
    			   pq.add(new Node(next.seq,minDistance[start][next.seq]));
    		   }
    	   }
       }
       //노드간 거리 출력
       for(int i=0;i<M;i++) {
    	   st = new StringTokenizer(br.readLine());
    	   
    	   int start = Integer.parseInt(st.nextToken());
    	   int end = Integer.parseInt(st.nextToken());
    	   
    	   System.out.println(minDistance[start][end]);
       }
	}
}
class Node{
	int seq;
	int distance;
	
	public Node(int seq, int distance) {
		this.seq = seq;
		this.distance = distance;
	}
}

 

 

실행 결과

---

 

팁

---

• 노드간의 거리는 BFS와 다익스트라를 생각해보자