[백준] 1240 노드사이의 거리 - 트리(Tree) + DFS JAVA

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

1240번: 노드사이의 거리

코드설명

트리와 DFS 를 활용하는 문제입니다.

 

트리문제를 풀때는 항상 트리의 성질을 기억해야합니다.

1. 루트노드를 제외한 트리의 부모는 항상 1 개입니다. ( 이를 통해 DFS를 진행할떄 Visited가 아닌 prevNode를 활용할 수 있습니다. 트리에서는 어떤 정점의 부모는 하나이거나 없다 )

2. 트리의 간선은 트리의 개수가 N개라면, 간선의 개수는 N-1 입니다.

3. 임의의 두 정점 U와 V에 대해, U에서 V로 가는 최단경로는 유일하다.
4. 아무 정점이나 잡고 부모와의 연결을 끊었을 때, 해당 정점과 그 자식들, 그 자식들의 자식들… 로 이루어진 부분그래프는 트리가 된다.

위의 특성들을 기억한다면 문제를 접할때 도움이 될 것 입니다.

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
	public static int N, M;
	public static int[] arr;
	public static ArrayList<ArrayList<Node>> graph = new ArrayList<ArrayList<Node>>();
	public static int answer = 0;
    public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer st = new StringTokenizer(br.readLine()); 	
    	
    	N = Integer.parseInt(st.nextToken());
    	M = Integer.parseInt(st.nextToken());
    	
    	for(int i=0;i<=N;i++) {
    		graph.add(new ArrayList<Node>());
    	}
    	
    	for(int i=0;i<N-1;i++) {
    		st = new StringTokenizer(br.readLine());
    		int a = Integer.parseInt(st.nextToken());
    		int b = Integer.parseInt(st.nextToken());
    		int dist = Integer.parseInt(st.nextToken());
    		graph.get(a).add(new Node(b, dist));
    		graph.get(b).add(new Node(a, dist));
    	}
    	
    	for(int i=0;i<M;i++) {
    		st = new StringTokenizer(br.readLine());
    		int a = Integer.parseInt(st.nextToken());
    		int b = Integer.parseInt(st.nextToken());
    		dfs(a, b, -1, 0);
    	}
    	
    }
    
    public static void dfs(int start, int target, int prevNode, int sum) {

    	if( start == target) {
    		System.out.println(sum);
    		return ;
    	}
    	
    	for(int i=0;i<graph.get(start).size();i++) {
    		Node nodeTemp = graph.get(start).get(i);
    		if(nodeTemp.nodeB != prevNode ) {
    			dfs(nodeTemp.nodeB, target, start, sum + nodeTemp.dist);
    		}
    	}
    }
        
}
class Node{
	int nodeB;
	int dist;
	public Node(int nodeB, int dist) {
		this.nodeB = nodeB;
		this.dist = dist;
	}
}