[백준] 1967번:트리의 지름 (Java 자바)

문제

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

1967번: 트리의 지름

 

풀이 및 소스코드

 

먼저, 트리의 루트로부터 제일 멀리 떨어진 ( 가중치가 제일 큰 ) 노드를 구한다.

예제는 위와 같다.

9번 노드가 가장 멀리 떨어져있음을 알 수 있다.

따라서, 가장 멀리 떨어진 노드부터 그 노드에서 가장 멀리 떨어진 노드가 트리의 지름이라고 할 수 있다.

이때, 자식노드에서 부모노드로 탐색을 해야하기 때문에 양방향 그래프를 만들어주되, dfs 돌릴 때 방문처리를 꼭 해줘야 한다.

 

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 Main {
	static int w_max, max_idx;
	static List<node>[] g;
	static boolean[] v;

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;

		int n = Integer.parseInt(br.readLine());

		g = new ArrayList[n + 1];
		for (int i = 0; i < n+1 ; i++) {
			g[i] = new ArrayList<node>();
		}

		for (int i = 0; i < n-1; i++) {
			st = new StringTokenizer(br.readLine());
			int p = Integer.parseInt(st.nextToken());
			int c = Integer.parseInt(st.nextToken());
			int w = Integer.parseInt(st.nextToken());
			g[p].add(new node(c, w));
			g[c].add(new node(p, w));
		}

		// 루트에서 부터 가장 먼 노드 찾기
		v = new boolean[n + 1];
		v[1] = true;
		dfs(0, 1);

		// 루트에서 가장 먼 노드부터 그 노드로부터 가장 먼 노드까지의 길이 구하기
		v = new boolean[n + 1];
		v[max_idx] = true;
		dfs(0, max_idx);
		System.out.println(w_max);
	}

	public static void dfs(int w_sum, int p) {
		// 가중치 합 비교
		if (w_sum > w_max) {
			w_max = w_sum;
			max_idx = p;
		}

		// 하위 혹은 상위 node로 가기
		for (node x : g[p]) {
			if (!v[x.c]) {
				v[x.c] = true; //방문처리 꼭꼭
				dfs(w_sum + x.w, x.c);
				v[x.c] = false;
			}
		}
	}
}

class node {
	int c, w;
	// 연결된 자식과 가중치 값이 들어감
	// 혹은 부모와 가중치 값이 들어감

	public node(int c, int w) {
		super();
		this.c = c;
		this.w = w;
	}

}