[백준] 1967. 트리의 지름 (자바 JAVA)

[ 문제 ]  [백준] 1967. 트리의 지름 (자바 JAVA)

 

문제 링크 : https://www.acmicpc.net/problem/1967

1967번: 트리의 지름

---

# 접근 방법 및 풀이 

 

• DFS로 풀었다. 
• 1~N까지 노드와 연결된 간선정보를 "양방향 인접리스트"로 표현했다.
• 간선에 가중치가 있으므로 연결된 노드 번호와 가중치를 담기 위해 Node라는 클래스를 만들어서 입력을 받았다.
• 1~N까지 모든 노드에 대해 각 노드마다 DFS를 통해 연결된 노드 끝까지 가보며 가중치를 더해간다. 그리고 더한 가중치값 중 가장 큰 max값이 answer가 된다.
• 자세한건 코드참조

# 주의할 점 

 

• 딱히 없음

 

JAVA 코드

package Gold;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

public class bj1967_트리의지름 {
	static int N;
	static class Node{
		int num, len;
		public Node(int num, int len) {
			this.num = num;
			this.len = len;
		}
	}
	static List<Node> list[];
	static boolean visit[];
	static int ans;
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(in.readLine());
		list = new ArrayList[N+1];
		for (int i = 1; i < N+1; i++) {
			list[i] = new ArrayList<Node>();
		}
		for (int i = 0; i < N-1; i++) {
			StringTokenizer st = new StringTokenizer(in.readLine());
			int from = Integer.parseInt(st.nextToken());
			int to = Integer.parseInt(st.nextToken());
			int len = Integer.parseInt(st.nextToken());
			list[from].add(new Node(to, len));
			list[to].add(new Node(from, len));
		}
		ans = 0;
		for (int i = 1; i <= N; i++) {
			visit = new boolean[N+1];
			visit[i] = true;
			dfs(i, 0);
		}
		System.out.println(ans);
	}
	private static void dfs(int num, int dim) {
		for (Node node : list[num]) {
			if(!visit[node.num]) {
				visit[node.num] = true;
				dfs(node.num, dim + node.len);
			}
		}
		ans = (ans < dim)? dim : ans;
	}
}

 

 

 

REVIEW