[Java] Baekjoon1967: 트리의 지름 / 오답의 이유 모두 분석

트리의 지름

2 초

128 MB

21643

8718

6622

43.785%

문제

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

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

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

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

입력

파일의 첫 번째 줄은 노드의 개수 n(1 ≤ n ≤ 10,000)이다. 둘째 줄부터 n-1개의 줄에 각 간선에 대한 정보가 들어온다. 간선에 대한 정보는 세 개의 정수로 이루어져 있다. 첫 번째 정수는 간선이 연결하는 두 노드 중 부모 노드의 번호를 나타내고, 두 번째 정수는 자식 노드를, 세 번째 정수는 간선의 가중치를 나타낸다. 간선에 대한 정보는 부모 노드의 번호가 작은 것이 먼저 입력되고, 부모 노드의 번호가 같으면 자식 노드의 번호가 작은 것이 먼저 입력된다. 루트 노드의 번호는 항상 1이라고 가정하며, 간선의 가중치는 100보다 크지 않은 양의 정수이다.

출력

첫째 줄에 트리의 지름을 출력한다.

풀이: 논리 오류로 인한 풀이 수정 + 트리 지름 증명

재귀의 방식으로 생각해보았습니다. 이분트리라는 말이 없기 때문에 이분트리로 가정하면 오답이 될 수 있습니다. 한 노드에 대해서 왼쪽과 오른쪽의 경로 중 최대값을 가져와 기록합니다. 또한 왼쪽과 오른쪽을 더한 값이 트리의 지름이 될 수 있으므로 최대값과 계속 비교합니다.

또한 1이 루트라고 해서 1이 무조건 긴게 아닙니다. 예를 들어 3을 기준으로 보면 아래 뿐만 아니라 1로 이어지는 선도 지름으로 사용할 수 있음을 주의해야합니다.

 

재귀

 

각각의 노드는 한 개의 상위노드를 가집니다

3번 노드를 기준으로 살펴보면

바로 하위 노드로 두 개가 있습니다 → 5 와 6

5와 6의 상위노드는 3이고 3과의 경로길이가 저장되어있습니다. → 5(11), 6(9)

위 값 뿐아니라 5와 6 안에는 지금까지의 최대 길이의 경로가 저장되어있습니다 → 5(11, 15) , 6(9,10)

이 두 값 중 큰 값이 노드 3의 지금까지 최대 길이에 저장됩니다. 11+15 = 26

그리고 둘 모두를 더한 값을 지금까지 기록한 지름의 최대값과 비교해 갱신합니다. 26 + 19 = 45

<예시 케이스>
10
1 2 2
1 3 21
1 4 3
2 5 1
2 6 40
3 7 22
4 8 20
4 9 30
4 10 35

import java.io.*;
import java.util.*;
public class Main {
	static ArrayList<Node>[] tree;
	static int MAX,index = 0; // 지름의 최대값을 기록하는 곳
	static int[][] dp; //자식 노드가 여러 개 일때 그 중 최대값 2개만 저장하는 곳
	static class Node{
		int num,len; //현재 숫자와 길이 저장

		Node(int num, int len){
			this.num = num;
			this.len = len;
		}
		
	}
	static int radiusMax(int n) {
		
		for(int i=0; i<tree[n].size(); i++) {
			int now = radiusMax(tree[n].get(i).num)+tree[n].get(i).len;
			
			if(now>dp[n][0]) { //최대값은 0에 그 다음으로 작은 값은 1에 저장
				dp[n][1]=dp[n][0];
				dp[n][0]=now;
			}else if(n>dp[n][1]) {
				dp[n][1]=now;
			}else if(now==dp[n][0]) {
				
			}
			
		}
		if(dp[n][0]+dp[n][1]>MAX) {
			MAX = dp[n][0]+dp[n][1];
			index = n;
		}
		
		
		return dp[n][0];
	}
	public static void main(String[] args) throws IOException {
	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	StringTokenizer st;
	int node = Integer.parseInt(br.readLine());
	dp = new int[node+1][2];
	tree = new ArrayList[node+1];
	for(int i=0;i<=node;i++) {
		tree[i] = new ArrayList();
	}
	int N = node - 1;

	while(N-->0) {
		st = new StringTokenizer(br.readLine());
		int parent = Integer.parseInt(st.nextToken());
		int child = Integer.parseInt(st.nextToken());
		int len = Integer.parseInt(st.nextToken());
		tree[parent].add(new Node(child,len));
	}	
	radiusMax(1);
	radiusMax(index);
	System.out.println(MAX);
}}

 

풀이2

이 문제는 트리의 지름은 루트에서 가장 먼 점에 존재한다는 증명으로 풀이할 수 있습니다.

트리의 지름이 될 수 있는 점을 먼저 찾아야 합니다.

이를 위해 루트 1에서 시작해 경로들의 차이를 구하고 1에서 가장 멀리 떨어진 노드를 찾습니다.

그리고 그 노드를 루트로 다시 가중치들을 계산해줍니다.

import java.io.*;
import java.util.*;
public class Main {
	static ArrayList<Node>[] tree;
	static int MAX,index; // 지름의 최대값을 기록하는 곳
	static boolean check[]; //방문체크
	static class Node{
		int num,len; //현재 숫자와 길이 저장
		Node(int num, int len){
			this.num = num;
			this.len = len;
		}
		
	}
	static void dfs(int n, int sum) {
		check[n]=true;
		if(MAX<sum) {
			MAX = sum;
			index = n;
		}
		for(Node node : tree[n]) {
				if(!check[node.num]) {
					dfs(node.num,sum+node.len);
				}
		}
	}
	public static void main(String[] args) throws IOException {
	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	StringTokenizer st;
	int node = Integer.parseInt(br.readLine());
	tree = new ArrayList[node+1];
	for(int i=0;i<=node;i++) {
		tree[i] = new ArrayList<>();
	}
	int N = node - 1;

	while(N-->0) {
		st = new StringTokenizer(br.readLine());
		int parent = Integer.parseInt(st.nextToken());
		int child = Integer.parseInt(st.nextToken());
		int len = Integer.parseInt(st.nextToken());
		tree[parent].add(new Node(child,len));
		tree[child].add(new Node(parent,len));
	}
	check = new boolean[node+1];
	dfs(1,0);
	check = new boolean[node+1];
	dfs(index,0);
	System.out.println(MAX);
}}