백준 - 1167번 - 트리의 지름

1167번

import java.util.*;
import java.io.*;

public class Main{

	static ArrayList<Node>[] al;
	static boolean[] visited;
	static int node;
	static int max = 0;


	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		int num = Integer.parseInt(bf.readLine());

		al = new ArrayList[num+1];
		for (int i = 1; i<num+1; i++) {
			al[i] = new ArrayList<>();
		}
		for (int i = 0; i<num; i++) {
			StringTokenizer st = new StringTokenizer(bf.readLine());
			int m = Integer.parseInt(st.nextToken());

			while (true) {
				int end = Integer.parseInt(st.nextToken());
				if (end == -1) break;
				int cost = Integer.parseInt(st.nextToken());
				al[m].add(new Node(end, cost));
			}
		}

		visited = new boolean[num+1];
		dfs(1, 0);

		visited = new boolean[num+1];
		dfs(node, 0);

		System.out.println(max);
	}

	public static void dfs(int a, int len) {
		if (len > max) {
			max = len;
			node = a;
		}
		visited[a] = true;

		for (int i = 0; i<al[a].size(); i++) {
			Node n = al[a].get(i);
			if (visited[n.x] == false) {
				dfs(n.x, n.cost + len);
				visited[n.x] = true;
			}
		}
	}
	public static class Node {
		int x, cost;

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

풀이

---

트리가 주어지고 정점간 연결을 나타낼때 연결값을 정해준다. 두점사이 연결값이 최대일때를 몇인지 구하는 문제다.

Node 클래스를 자료형으로 하는 ArrayList[] al를 선언하고 정점수만큼 al에 ArrayList를 또 선언해준다.

입력받은 수를 Node모양으로 저장해준다.

제일멀리 떨어진 노드를 구하기 위해 dfs(아무숫자, 0)을 돌려본다.

dfs한번돌려 아무숫자에서 제일 먼 노드를 구한다.

어떻게 구해질까?
이 문제가 골드인 이유는 여기에 있다. 탐색을 진행할때 아래의 로직을 사용해주면 메서드가 돌아가면서 연결값을 더해주면서 탐색을 할텐데 누적 연결값이 최대일때만 node라는 변수를 변화시키기 때문에 무조건 포함해야하는 점(=node)을 알려주게된다. 참고로 여기서 max값은 실제 max값과 다르다.

if (len > max) {
	max = len;
	node = a;
}

dfs(무조건 포함해야하는 node, 0)으로 돌리면 최대값이 나온다.

이번문제로 재귀를 더 깊게 알 수 있었다. 그리고 조건문으로 문제를 푸는데 중요한 변수를 알아내는것을 앞으로 생각해야겠다.