개발자꿀꿀이

DFS 를 이용해서 문제를 풀지만 트리의 지름을 찾는 알고리즘을 알아야했다. 트리의 지름이란, 트리에서 거리중 가장 긴 것을 말한다. 정점마다 각각의 정점으로 향하는 가중치의 값을 모두 구하기에는 시간제한에 걸릴것 같아 DFS 를 이용하여 임의의점(여기서 나는 1로 두었다) 에서 제일 거리간 긴점, 그 점에서 제일 멀리있는 점이 트리의 지름이라는 글을 읽고 문제를 풀었다. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.List; class Node{ public int v, d; public Node(int..

처음에는 Node 의 클래스 생성을 통해 트리구조를 만들고 찾아가는 방식을 사용하였다. 이렇게 할 경우 자식의 list 를 반복문으로 다 찾아야하기 때문에 시간초과가 되는 오류가 발생했다. 실행시간을 줄이기 위해 그래프구조의 DFS 방식을 사용하였다. ​ import java.util.LinkedList; import java.util.Scanner; public class Main { static int n; static Node tree; public static void main(String[] args){ Scanner scanner = new Scanner(System.in); n = scanner.nextInt(); String line = null; line = scanner.nextLine..