[BaekJoon] 1240 노드사이의 거리 (Java)

1.  문제 링크

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

2.  문제

요약

• N개의 노드로 이루어진 트리가 주어지고 M개의 두 노드 쌍을 입력받을 때 두 노드 사이의 거리를 구하는 문제입니다.
• 입력: 첫 번째 줄에 2보다 크거나 같고 1,000보다 작거나 같은 노드의 개수 N과 1,000보다 작거나 같은 M이 주어지고 두 번째 줄부터 N - 1개의 줄에는 트리 상에 연결된 두 점과 10,000보다 작거나 같은 정수인 두 점 사이의 거리가 주어지며 그 다음 줄부터 M개의 줄에는 노드 쌍이 한 줄에 한 쌍씩 주어집니다.
• 출력: 첫 번째 줄부터 M개의 줄에 차례대로 입력받은 두 노드 사이의 거리를 출력합니다.

3.  소스코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;

public class Main {
	static ArrayList<Edge>[] map;
	static int result;
	
	public void getPairDistance(int start, int end, int prev_node, int distance) {
		if(start == end) {
			result = distance;
		}
		for(Edge e : map[end]) {
			if(e.node != prev_node) {
				getPairDistance(start, e.node, end, distance + e.distance);
			}
		}
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		String[] input = br.readLine().split(" ");
		int node_num = Integer.parseInt(input[0]);
		int pair_num = Integer.parseInt(input[1]);
		map = new ArrayList[node_num + 1];
		for(int i = 1; i <= node_num; i++) {
			map[i] = new ArrayList<Edge>();
		}
		for(int i = 0; i < node_num - 1; i++) {
			input = br.readLine().split(" ");
			int start = Integer.parseInt(input[0]);
			int end = Integer.parseInt(input[1]);
			int distance = Integer.parseInt(input[2]);
			map[start].add(new Edge(end, distance));
			map[end].add(new Edge(start, distance));
		}
		Main m = new Main();
		for(int i = 0; i < pair_num; i++) {
			input = br.readLine().split(" ");
			int start = Integer.parseInt(input[0]);
			int end = Integer.parseInt(input[1]);
			m.getPairDistance(start, end, -1, 0);
			bw.write(result + "\n");
		}
		bw.flush();
		bw.close();
	}
	
	public static class Edge {
		int node;
		int distance;
		public Edge(int node, int distance) {
			this.node = node;
			this.distance = distance;
		}
	}
}

4.  접근

• 해당 문제는 DFS를 이용하여 해결할 수 있습니다.
• 각 index에 해당하는 노드부터 연결된 각각의 다른 노드까지의 노드 번호와 거리를 담는 ArrayList 배열 map을 생성합니다.
• 해당 문제의 그래프는 방향성이 없는 그래프이기 때문에 주어진 두 노드 모두 서로 연결된 것이므로 두 노드 모두에 각 노드의 번호와 거리를 넣어줍니다.
• 도착 노드부터 시작하여 도착 노드에 연결되어 있는 각 노드들을 탐색하고 만약 해당 노드가 바로 이전에 방문했던 노드가 아니라면 DFS를 통해 해당 노드에 연결되어있는 다른 노드들을 탐색합니다.
• 이렇게 탐색을 진행하다가 시작 노드와 같아지는 시점의 거리를 계산하여 이를 출력합니다.

public void getPairDistance(int start, int end, int prev_node, int distance) {
	if(start == end) {
		result = distance;
	}
	for(Edge e : map[end]) {
		if(e.node != prev_node) {
			getPairDistance(start, e.node, end, distance + e.distance);
		}
	}
}