풀이방법
전에 풀었던 트리의 지름을 이용해서 풀었다. 그런데 시간 초과가 나버린다. 어디서 고쳐야 할지 모르겟당...
조금 더 공부하고 나중에 다시 봐야지
지금 실력으로는 시간초과를 극복할 방법을 못찾겟당...
코드
package pro;
import java.util.*;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;
public class test10 {
static class Node{ //static 꼭 붙여야함.
int num;
int length;
public Node(int num, int length) {
this.num = num;
this.length = length;
}
}
static int V;
static List<Node> list[]; //노드형으로 리스트라는 이름의 배열생성.
static boolean[] visit; // 방문햇는지 체크 리스트라는 이름의 배열과 크기가 같음.
static int answer =0;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
V = Integer.parseInt(br.readLine()); // 정점의 갯수
list = new ArrayList[V+1];
//visit = new boolean[V+1]; // v+1 로 주는 이유는 1 을 첫 인덱스로 만들기 위해
//여기서 초기화 해주면 안됨. dfs 돌리면서 초기화 해주어야함.
for(int i = 1; i<V+1; i++) {
list[i] = new ArrayList<Node>();
}//이차배열처럼 하나 더 생성해주어야함. 꼭!
for(int i = 1; i< V +1; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
int start = Integer.parseInt(st.nextToken());
while(true) {
int end = Integer.parseInt(st.nextToken());
if(end==-1) break;
int length = Integer.parseInt(st.nextToken());
list[start].add(new Node(end,length));
// list[end].add(new Node(start, length));
}
}
for(int i =1 ;i<= V ; i++) {
visit = new boolean[V+1]; // 여기서 초기화
visit[i] = true; //시작점은 방문 표시해주고 dfs 돌림
dfs(i , 0);
}
System.out.println(answer);
}
public static void dfs(int start, int sum) {
for(Node node : list[start]) {
if(!visit[node.num]) {
visit[node.num] = true;
dfs(node.num, sum+node.length);
}
}
answer = answer<=sum?sum:answer;
}
}