[백준] 1967 트리의 지름

📌 문제

트리(tree)는 사이클이 없는 무방향 그래프이다. 트리에서는 어떤 두 노드를 선택해도 둘 사이에 경로가 항상 하나만 존재하게 된다. 트리에서 어떤 두 노드를 선택해서 양쪽으로 쫙 당길 때, 가장 길게 늘어나는 경우가 있을 것이다. 이럴 때 트리의 모든 노드들은 이 두 노드를 지름의 끝 점으로 하는 원 안에 들어가게 된다.

이런 두 노드 사이의 경로의 길이를 트리의 지름이라고 한다. 정확히 정의하자면 트리에 존재하는 모든 경로들 중에서 가장 긴 것의 길이를 말한다.

입력으로 루트가 있는 트리를 가중치가 있는 간선들로 줄 때, 트리의 지름을 구해서 출력하는 프로그램을 작성하시오. 아래와 같은 트리가 주어진다면 트리의 지름은 45가 된다.

트리의 노드는 1부터 n까지 번호가 매겨져 있다.

✔ 접근방법

처음 문제를 풀었을 때, leaf노드들을 구해서 이 leaf노들들끼리 dfs를 수행하여 가장 큰값을 구하도록 문제를 풀이했었다.
테스트는 성공했지만, 다른 풀이를 찾아보니 더욱 효율적인 방법이있었다.

1. 루트노드에서 가장 길이간 긴 노드를 찾는다.
2. 1에서 찾은 노드를 기준으로 가장 거리간 먼 노드를 찾는다.

이렇게 총 DFS를 두번 실행하면, 문제가 요구하는 답을 구할 수 있다.

✔ 코드

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;

public class Main {
	static class Node {
		int y;
		int cost;

		Node(int y, int cost) {
			this.y = y;
			this.cost = cost;
		}
	}

	static ArrayList<ArrayList<Node>> tree = new ArrayList<>();
	static int n;
	static int max = 0;
	static int endNode = 0;
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		n = sc.nextInt();

		boolean[] visit = new boolean[n];

		for (int i = 0; i < n; i++) {
			tree.add(new ArrayList<Node>());
		}

		for (int i = 0; i < n - 1; i++) {
			int x = sc.nextInt() - 1;
			int y = sc.nextInt() - 1;
			int cost = sc.nextInt();
			tree.get(y).add(new Node(x, cost));
			tree.get(x).add(new Node(y, cost));
		}

		
		//1. 루트 노드에서 가장 거리가 먼 노드를 찾는다.
		dfs(0, 0, visit);
		
		Arrays.fill(visit, false);
		
		//2. 1에서 찾은 가장 먼 노드를 기준으로 가장 거리가 먼 노드를 찾아 트리의 지름을 구한다.
		dfs(endNode, 0, visit);
		
		System.out.println(max);
	}

	private static void dfs(int cur, int sum, boolean[] visit) {
		
		visit[cur] = true;
		if (max < sum) {
			max = sum;
			endNode = cur;
		}

		

		for (int i = 0; i < tree.get(cur).size(); i++) {
			if (visit[tree.get(cur).get(i).y]) continue;
			dfs(tree.get(cur).get(i).y, sum + tree.get(cur).get(i).cost, visit);
		}
	}
}

🖋 회고

답을 구하고 문제를 풀이하더라도, 더욱 효율적인 방법이 있는지 찾아보고 코드를 수정하는 시간 또한 중요하다고 생각한다.
아직 DFS, BFS같은 그래프 탐색이 서툰 면이 없지 않아 있는데, 문제를 풀다보면 해결 될거라 믿는다 아Zㅏ!

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