[BOJ]1167_트리의지름_Java

--문제--

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

Class4

1167번: 트리의 지름

--문제 접근--

처음 문제를 봤을 때에 가중치만 더해주면 될 것이라고 판단하여 더하기만 하면 틀렸습니다가 나왔습니다.

그래서 문제를 다시 한번 읽고 트리의 지름에 대해 알아보고 한 번 더 코드를 짜기를 시작하였습니다.

 

위의 사진을 볼 때 한쪽만을 고려하면 1번 만을 고려하는 경우가 돼서 1번과 2번 양쪽을 고려하기 위하여 1번 사진의 맨 끝 노드를 구한 이후에 그 노드를 기준으로 한 번 더 가중치의 최댓값을 구해줬습니다.

package Class4;

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

public class BOJ_1167트리의지름 {
	static class Node{
		int node,weight;

		public Node(int node, int weight) {
			super();
			this.node = node;
			this.weight = weight;
		}
		
	}
	static List<Node>[] graph;
	static int ans;
	static boolean[] visit;
	static Node maxNode;
	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		int N=sc.nextInt();
		graph=new ArrayList[N+1];
		visit=new boolean[N+1];
		for(int i=0;i<=N;i++)graph[i]=new ArrayList<>();
		for(int i=0;i<N;i++) {
			int from=sc.nextInt();
			while(true) {
				int to=sc.nextInt();
				if(to==-1)break;
				int weight=sc.nextInt();
				graph[from].add(new Node(to,weight));
			}
		}
		graph[0].add(new Node(1,0));
		ans=0;
		Node maxN;
		maxN=dfs(graph[0].get(0),0);
		visit=new boolean[N+1];
		maxNode=null;
		ans=0;
		dfs(maxN,0);
		System.out.println(ans);
	}
	public static Node dfs(Node v,int weight) {
		if(ans<weight) {
			ans=weight;
			maxNode=v;
		}
		visit[v.node]=true;
		for(Node cur:graph[v.node]) {
			if(!visit[cur.node])
				dfs(cur,weight+cur.weight);
			
		}
		return maxNode;
	}
	
}