[BOJ] [JAVA] 1167번 트리의 지름

1167번: 트리의 지름

트리의 지름을 구하는 방식이 재밌다.

임의의 한 노드에서 가장 멀리 떨어진 노드를 찾는다.

찾은 노드에서 가장 멀리 떨어진 노드를 찾으면 이 두 노드 사이의 거리가 트리의 지름이 된다.

트리라고 해서 부모와 자식 관계를 자꾸 떠올려서 이상한 방향으로 계속 생각했는데

트리도 결국 그래프이므로 인접한 노드를 방문한다는 아이디어를 가지고 가야 했다.

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

public class Main {
	
	// dfs 시 사용되는 방문 여부
	static boolean[] visit;
	
	// list[p] : p의 자식 노드가 담긴 연결 리스트
	static List<Node> [] list;
	
	// 시작 위치에서 가장 먼 거리
	static int maxDist;
	// 시작 위치에서 가장 먼 거리에 있는 노드 번호
	static int maxDistNode;
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;

		int n = Integer.parseInt(br.readLine());
		
		list = new List[n + 1];

		// LinkedList 생성
		for (int i = 1; i <= n; i++) 
			list[i] = new LinkedList<>();
		
		// p의 자식 노드 정보
		for (int i = 1; i <= n; i++) {
			st = new StringTokenizer(br.readLine());
			int p = Integer.parseInt(st.nextToken());
			
			while (st.hasMoreTokens()) {
				int node = Integer.parseInt(st.nextToken());
				if (node == -1) break;
				int di = Integer.parseInt(st.nextToken());
				// p 의 자식 노드 : 노드 번호와 p와의 거리
				list[p].add(new Node(node, di));
			}
		}
		// 루트와 가장 먼 거리에 있는 노드
		visit = new boolean[n + 1];
		visit[1] = true;
		maxDist = 0;
		maxDistNode = 1;
		// 루트와 가장 먼 노드와 그 거리를 찾는다.
		dfs(1, 0);
		
		// 루트와 가장 먼 노드로부터 다시 가장 먼 거리에 있는 노드를 찾는다.
		visit = new boolean[n + 1];
		maxDist = 0;
		visit[maxDistNode] = true;
		dfs(maxDistNode, 0);
		// 이 때의 값이 트리의 지름
		System.out.println(maxDist);
	}
	
	// dfs로 최대 거리 탐색
	static void dfs(int cur, int di) {
		for (Node nd : list[cur]) {
			
			// 방문하지 않은 노드를 탐색한다.
			if (!visit[nd.num]) {
				visit[nd.num] = true;
				dfs(nd.num, di + nd.dist);
				visit[nd.num] = false; 
			}
		}
		// 더 방문할 곳이 없을 때 최대 거리와 노드 번호 계산
		if (maxDist < di) {
			maxDist = di;
			maxDistNode = cur;
		}
	}
}

// 노드는 인접 노드 번호와 거리를 가진다.
class Node {
	int num;
	int dist;
	
	public Node(int num, int dist) {
		super();
		this.num = num;
		this.dist = dist;
	}
}