[1167번] 트리의 지름 ( 가중치 있는 그래프, bfs, 최장 거리:트리의 지름을 찾는 알고리즘, 배열 원소 중 최대값의 인덱스 찾기 )

---

bfs로 구현한다.
트리의 지름을 찾는 알고리즘을 모르면, 못 푸는 문제라고 해도 무방할 듯하다.

---

✅ 트리의 지름을 찾는 알고리즘

참고 링크 : https://blogshine.tistory.com/111

임의의 정점 (정점 2) 에서 최장 거리의 정점(정점 5)을 찾는다.
그 최장 거리 정점(정점 5)에서 가장 최장 거리인 정점(정점 1)을 찾는다.
그때 때의 거리 값(정점 5에서 정점 1까지의 가중치)이 최장이 된다.

---

✅ 배열 원소 중 최대값의 인덱스 찾기

int MaxIndex = 1; //배열을 V+1까지 만듦!

for (int i = 2; i < wLength.length; i++) {
		if (wLength[MaxIndex] < wLength[i]) {
				MaxIndex = i;
		}
}

---

✅ 주의

[ 주의할 점 ]
ArrayList는 N+1까지이므로 N까지 초기화!
다시 bfs를 시작할 때도 visited 배열과 wLength 배열 초기화 시켜주자!

👾 이때까지 구현한 bfs와 다른 점

if (!visited[end]) {
		visited[end] = true;
		wLength[end] = wLength[nowNode] + w; //이전 값에서 값을 축적!
		queue.add(end);
}

---

✅ 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

class Node {
	int endPoint;
	int weight;

	public Node(int endPoint, int weight) {
		this.endPoint = endPoint;
		this.weight = weight;
	}

}

public class Main {
	static ArrayList<Node>[] A;
	static boolean visited[];
	static int wLength[];

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

		A = new ArrayList[V + 1];
		visited = new boolean[V + 1];
		wLength = new int[V + 1];

		for (int i = 0; i < V + 1; i++) {
			A[i] = new ArrayList<>();
		}

		for (int i = 0; i < V; i++) {
			st = new StringTokenizer(br.readLine());
			int startNode = Integer.parseInt(st.nextToken());
			while (true) {
				int end = Integer.parseInt(st.nextToken());
				if (end == -1) break;
				int w = Integer.parseInt(st.nextToken());
				A[startNode].add(new Node(end, w));
			}
		}

		bfs(2);

		//첫 번째 노드의 bfs가 끝날 시 최장 거리의 노드로 한 번 더 bfs 실행

		int MaxIndex = 1; //배열을 V+1까지 만듦!
		for (int i = 2; i <= V; i++) {
			if (wLength[MaxIndex] < wLength[i]) {
				MaxIndex = i;
			}
		}

		//초기화!!!!
		visited = new boolean[V + 1];
		wLength = new int[V + 1];
		bfs(MaxIndex);

		Arrays.sort(wLength);
		System.out.println(wLength[V]);

	}

	private static void bfs(int startNode) {
		Queue<Integer> queue = new LinkedList<>();
		queue.offer(startNode);
		visited[startNode] = true;

		while (!queue.isEmpty()) {
			int nowNode = queue.poll();
			for (Node i : A[nowNode]) {
				int end = i.endPoint;
				int w = i.weight;
				if (!visited[end]) {
					visited[end] = true;
					wLength[end] = wLength[nowNode] + w; //이전 값에서 값을 축적!
					queue.add(end);
				}
			}
		}

	}
}

---

✅ 한 번 더 손으로 풀어보자면

---