백준 - 트리의 기둥과 가지

문제 설명

트리의 기둥의 길이와 기가 노드로부터 뻗어있는 가장 멀리 뻗어 있는 가지의 길이를 구하는 문제이다.

주의사항

트리의 기둥부터 기가노드 까지의 판별은 보통 나가는 간선의 개수가 3개 이상일 때 기가노드로 판단할 것이다.

하지만 예외 상황이 있다.

루트에서 기가노드의 길이가 0일 때이다.

1번이 루트라고 주어진다면, 1→2(1), 1→3(1) 으로 갈경우 그러면 기둥의 길이는 2가 되고 가지의 길이는 0이될 것이다.

정답 기둥의 길이가 0이고 가지의 길이가 0이 되어야 한다.

생각한 아이디어

DFS

풀이

private static int root;

	static class Node {
		private int v, edge;

		public Node(int v, int edge) {
			this.v = v;
			this.edge = edge;
		}
	}

	static List<Node> adj[];
	static Node pillar;
	static boolean[] v;
	static int maxBranch;

	public static void main(String[] args) throws IOException {
		/**
		 * 나무의 기둥의 길이와 긴 가지의 길이를 파악하라.
		 *
		 * 기둥 - 루트에서 기가 노드 까지 이다. (:= 자식 노드가 하나인것)
		 * 	- 루트가 기가노드일 수 도 있다.
		 * 가지 - 기가노드 부터 임의의 리프 노드 까지이다.
		 * 기둥이 없고 가지가 2개일떄.
		 * 3 1
		 * 1 2 5
		 * 1 3 5
		 * ansewr: 0,5
		 */
		BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));

		StringTokenizer st = new StringTokenizer(reader.readLine());
		int n = Integer.parseInt(st.nextToken());
		root = Integer.parseInt(st.nextToken());

		adj = new List[n + 1];
		for (int i = 1; i < n + 1; i++) {
			adj[i] = new ArrayList<>();
		}

		for (int i = 0; i < n - 1; i++) {
			st = new StringTokenizer(reader.readLine());
			int v1 = Integer.parseInt(st.nextToken());
			int v2 = Integer.parseInt(st.nextToken());
			int edge = Integer.parseInt(st.nextToken());
			adj[v1].add(new Node(v2, edge));
			adj[v2].add(new Node(v1, edge));
		}
		v = new boolean[n + 1];
		measurePillar(root, 0);
		getLongestBranch(pillar.v, 0);

		System.out.println(pillar.edge + " " + maxBranch);
	}

	public static void measurePillar(int parent, int dist) {
		v[parent] = true;
		pillar = new Node(parent, dist);

		if (adj[parent].size() > 2 || (parent==root && adj[parent].size()>1)) {
//(parent==root && adj[parent].size()>1) root가 곧 기가노드일 경우 예외 처리
			return;
		}

		for (Node next : adj[parent]) {
			if (v[next.v])
				continue;

			measurePillar(next.v, dist + next.edge);
		}
	}

	public static void getLongestBranch(int parent, int dist) {
		maxBranch = Math.max(maxBranch, dist);
		v[parent] = true;

		for (Node next : adj[parent]) {
			if (v[next.v])
				continue;

			getLongestBranch(next.v, dist + next.edge);
		}
	}