[백준 1967번][Java] 트리의 지름 - 재귀 호출 전/후 함수 호출

 

www.acmicpc.net/problem/1967

1967번: 트리의 지름

 

이 문제를 풀면서 너무 아쉬웠다. 아마 10월 코드 챌린지 3번과 비슷한 문제가 아닌가 싶었다.

트리 부분을 너무 소홀히했다. 크 3솔이 눈에 아른거린다.

 

풀이 방법은 트리를 순회하면서 현재 노드를 기점으로 가장 긴 간선을 계산하고 자손의 수에 따라 가장 큰 2개나 한개를 현재 노드가 중심이 되는 지름이라고 한다.

 

아 이게 말로 설명하기는 조금 버겁다. 재귀를 이해한다면 코드를 보는게 낫다.

---

트리를 아직 몇 문제 풀어보면서 느낀건데 재귀 호출 이후에 존재하는 경우가 많다.

어떤 작업이 재귀 호출 전에 호출되느냐, 재귀 호출 후에 호출되느냐는 완전히 다르다.

재귀 호출 전에 호출되는 경우 루트부터 값을 구성해서 리프 노드로 전달해가는 탑-다운 방향이라면,

재귀 호출 후에 호출되는 경우는 리프 노드부터 값을 리턴해 루트까지 전달해가는 다운-탑 방향이다.

 

 

import java.io.*;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
import java.util.StringTokenizer;

/*
트리의 지름
https://www.acmicpc.net/problem/1967
 */
public class Main {
	static int n, maxDiameter = 0;
	static Node[] nodes;
	public static void main(String[] args) throws IOException {
		InputReader reader = new InputReader();
//		InputReader reader = new InputReader("testcase.txt");
		n = reader.readInt();
		nodes = new Node[n];
		for (int i = 0; i < n; i++) {
			nodes[i] = new Node(i);
		}

		for (int i = 0; i < n-1; i++) {
			StringTokenizer st = new StringTokenizer(reader.readLine());
			int u = Integer.parseInt(st.nextToken())-1;
			int v = Integer.parseInt(st.nextToken())-1;
			int w = Integer.parseInt(st.nextToken());
			nodes[u].children.add(new Edge(v,w));
		}
		getTreeDiameter(0);
		System.out.println(maxDiameter);
	}
	private static int getTreeDiameter(int index) {

		int maxHeight = 0;
		List<Integer> radius = new ArrayList<>();
		for (int i = 0; i < nodes[index].children.size(); i++) {
			Edge e = nodes[index].children.get(i);
			int height = getTreeDiameter(e.v) + e.w;
			radius.add(height);
			maxHeight = Math.max(height, maxHeight);
		}
		//지름 계산해서 저장
		radius.sort(Comparator.reverseOrder());
		if(radius.size() >= 2) maxDiameter = Math.max(radius.get(0) + radius.get(1), maxDiameter);
		if(radius.size() == 1) maxDiameter = Math.max(radius.get(0), maxDiameter);

		return maxHeight;
	}
}
class Node {
	int id;
	List<Edge> children = new ArrayList<>();
	public Node(int id) {
		this.id = id;
	}
}
class Edge {
	int v,w;
	public Edge(int v, int w) {
		this.v = v;
		this.w = w;
	}
}
class InputReader {
	private BufferedReader br;

	public InputReader() {
		br = new BufferedReader(new InputStreamReader(System.in));
	}

	public InputReader(String filepath) {
		try {
			br = new BufferedReader(new FileReader(filepath));
		} catch (FileNotFoundException e) {
			e.printStackTrace();
		}
	}

	public List<Character> readLineIntoCharList() throws IOException {
		List<Character> l = new ArrayList<>();
		while(true) {
			int readVal = br.read();
			if(readVal == '\n' || readVal == -1) break;
			l.add((char)readVal);
		}
		return l;
	}

	public boolean ready() throws IOException {
		return br.ready();
	}

	public String readLine() throws IOException {
		return br.readLine();
	}
	public int readInt() throws IOException {
		return Integer.parseInt(readLine());
	}
	public Long readLong() throws IOException {
		return Long.parseLong(readLine());
	}
}