백준 1167, 트리의 지름 - Tree, DFS

https://www.acmicpc.net/problem/1167

1. 아이디어

가중치 그래프(트리)에서 정점 간 거리 (간선 가중치) 특징

• 가장 거리가 먼 두 정점이 v1, v2인 경우,
  임의의 다른 정점 v_any와 가장 먼 정점은 v1 또는 v2이다.

1) 임의의 정점과 가장 먼 정점 1개 구하기 (구한 가장 먼 정점: v1)

• 임의의 정점 v_any에서 시작하여 DFS 수행
  
  

2) 정점 v1과 가장 먼 정점 구하기 (v1과 가장 먼 정점: v2)

• 정점 v1에서 시작하여 DFS 수행
  => v1과 v2는 트리에서 거리가 가장 먼 두 정점
  => DFS 2번으로 가장 먼 두 정점 v1, v2 (트리의 지름) 구함

오답 노트: 시간 초과한 풀이

• 모든 정점 1 ~ v의 각 정점들에 대해 DFS 탐색 수행
• 마지막 v 번 정점까지 DFS 완료해가면서 max 지름 값 갱신
  
  
• 전체 시간 복잡도 = 정점 개수(최대 10^5)만큼 DFS 수행
  => 2 x 10^5 x 10^5 = 2 x 10^10 >> 2억 (2초)

2. 자료구조

• List<Pair>[], ArrayList<Pair>[]: 인접 리스트
  ex) lists[1]: 1번 정점과의 연결 정보 Pair (정점 번호, 간선 거리)들 저장
• boolean[]: 방문 확인

3. 시간 복잡도

• DFS 1번 수행: O(V + E) = 2 x 10^5
  • V: 최대 10^5, E: 대충 10^5

• 전체 시간 복잡도 = DFS 2번 수행
  => 2 x (2 x 10^5) = 4 x 10^5 < 2억 (2초)

코드

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

class Pair {
	public int vertex;	// 연결된 정점 번호
	public int distance;	// 간선 거리

	public Pair(int vertex, int distance) {
		this.vertex = vertex;
		this.distance = distance;
	}
}

public class Main {
	static int v;			// 트리 정점(노드) 개수, 정점 번호: 1 ~ v
	static int maxR = Integer.MIN_VALUE;
	// 출력 값: 트리의 최대 지름 (두 정점 사이의 거리 중, 가장 긴 것)
	static List<Pair>[] lists;	// 인접 리스트
	static boolean[] check;
	static int vertex;		// 임의의 정점과 가장 먼 정점 (가장 먼 두 정점 v1, v2 둘 중에 하나)

	/* vertexIdx: 현재 정점 번호, totalDistance: 누적 거리 */
	static void dfs(int vertexIdx, int totalDistance) {
		check[vertexIdx] = true;

		List<Pair> list = lists[vertexIdx];
		for (Pair p : list) {
			if (!check[p.vertex])
				dfs(p.vertex, totalDistance + p.distance);
		}

		if (maxR < totalDistance) {
			maxR = totalDistance;
			vertex = vertexIdx;	// 첫 번째 DFS 로 가장 먼 두 정점 중, v1 구함
		}
	}

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

		v = Integer.parseInt(br.readLine());
		lists = new ArrayList[v + 1];		// [1 ~ v] 사용
		for (int i = 1; i <= v; i++)
			lists[i] = new ArrayList<>();

		for (int i = 1; i <= v; i++) {
			st = new StringTokenizer(br.readLine());

			int startNode = Integer.parseInt(st.nextToken());
			while (st.hasMoreTokens()) {
				int destNode = Integer.parseInt(st.nextToken());
				if (destNode == -1)
					break;
				int distance = Integer.parseInt(st.nextToken());

				lists[startNode].add(new Pair(destNode, distance));
				lists[destNode].add(new Pair(startNode, distance));
			}
		}

		// 임의의 정점에서 가장 먼 정점 v1 구하기 (vertex 에 저장)
		check = new boolean[v + 1];
		dfs(1, 0);

		// 정점 v1 과 가장 먼 정점 v2 구하기 => v1 과 v2 는 트리에서 가장 먼 두 정점
		// 트리의 최대 지름 계산
		check = new boolean[v + 1];
		dfs(vertex, 0);

		System.out.println(maxR);
	}
}