백준 | 1240번. 노드 사이의 거리 - DFS 풀이

⬛ 백준 1240번. 노드 사이의 거리 - DFS 풀이

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

1240번: 노드사이의 거리

문제

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

입력

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

출력

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

---

💚나의 풀이

• M개의 쌍으로 들어오는 s, e 노드사이의 거리를 출력해야 하는 문제이다.
• DFS(s, e, dist) 의 인수를 갖도록 메소드를 정의한다.
• M개의 쌍으로 입력이 들어온 시작점과 끝점에 대하여, 끝점은 고정이고 DFS로 쭉 깊이 탐색하면서 시작점이 점차 깊이 뻗어가다가 if( s == e )가 되는 시점에서의 dist 거리를 정적 변수인 max에 옮겨서 출력시키면 된다.

🟦 코드

package to_1128_D;

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

/**
 * 1240번. 노드 사이의 거리 - DFS
 * @author MYLG
 *
 */
class Edge{
	int e, val;
	Edge(int e, int val){
		this.e = e;
		this.val =val;
	}
}

public class Main {
	static int N, M;
	static boolean[] visited;
	static int max;
	static ArrayList<ArrayList<Edge>> graph;
	
	//DFS
	static void DFS(int s, int e, int dist) {
		if(s == e) {
			max = dist;
			return;
		}else {
			for(Edge nx : graph.get(s)) {
				if(!visited[nx.e]) {
					visited[nx.e] = true;
					DFS(nx.e, e, dist + nx.val);
				}
			}
		}
	}
	
	//실행 메인 
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner kb= new Scanner(System.in);
		N = kb.nextInt();
		M = kb.nextInt();
		
		graph = new ArrayList<>();
		for(int i=0; i<=N; i++) {
			graph.add(new ArrayList<>());
		}
		
		//데이터 입력받기 
		for(int i=0; i<N-1; i++) {
			int a = kb.nextInt();
			int b = kb.nextInt();
			int v = kb.nextInt();
			graph.get(a).add(new Edge(b,v));
			graph.get(b).add(new Edge(a, v));
		}
		
		for(int i=0; i<M; i++) {
			visited= new boolean[N+1];
			int s = kb.nextInt();
			int e = kb.nextInt();
			
			max = 0;
			visited[s] = true;
			DFS(s, e, 0);
			
			System.out.println(max);
		}
	}
}