[백준/JAVA] 1167_트리의 지름

백준🔗

1167번: 트리의 지름

 

문제

 

 

간단 풀이

 

어제 1967번 트리의 지름 문제(https://www.acmicpc.net/problem/1967)를 풀었어서 비슷한 방식으로 접근하고자 했다.

연결된 간선이 하나인 리프 노드들을 찾아서 각각의 노드에 대해 DFS를 수행해서 해당 노드를 출발 지점으로 했을 때의 최대 거리를 모두 구해보는 방식이다. 그러나 정점 개수가 100000개로 많아졌기 때문에 시간 초과가 발생했다.

 

한 번 DFS를 수행한 노드를 그래프에서 제거하면서 연산 횟수를 줄여보는 방법도 시도해봤지만 전체적인 DFS 실행 횟수가 같아서 그다지 효과는 없었다.

 

결국 구글에게 도움을 조금 얻어 보았다..

1) 임의의 한 정점에서 DFS를 실행해서 가장 먼 정점을 구한다.

2) 1에서 구한 정점에서 DFS를 다시 실행해서 가장 먼 정점까지의 거리를 구한다.

위의 2단계가 문제 풀이의 핵심이었다. 

임의의 정점에서 가장 먼 정점을 구하면 무조건 그 점이 트리의 지름을 구성하는 두 정점 중 하나이다. 따라서 그 정점에서 가장 먼 정점을 구하면 그것이 트리의 지름이 되는 것이다.

DFS를 2번만 실행하면 되기 때문에 2*O(n)의 시간복잡도를 가지는 로직이라고 할 수 있을 것이다.

 

 

코드

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {
	static List<Edge>[] graph;
	static boolean[] visited;
	static int R;
	static int node;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int V = sc.nextInt(); // 정점 개수
		graph = new List[V + 1];

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

		// 간선 정보 입력받기
		for (int i = 0; i < V; i++) {
			int st = sc.nextInt();
			// 마지막 입력이 아닐 때까지 반복해서 입력 받기
			while (true) {
				int ed = sc.nextInt();
				if (ed == -1)
					break;
				int d = sc.nextInt();
				graph[st].add(new Edge(ed, d));
			}
		}

		R = 0; // 트리의 지름
		node = 0; // 정점 번호

		// 임의의 정점에서 가장 먼 점을 구한다! 이 점이 지름을 구성하는 2개의 점 중 하나이다.
		visited = new boolean[V + 1];
		DFS(1, 0);

		// 위에서 구한 점에서 가장 먼 점까지의 거리를 구한다. 이것이 트리의 지름!
		visited = new boolean[V + 1];
		DFS(node, 0);

		System.out.println(R);
	}

	private static class Edge {
		int ed, d;

		public Edge(int ed, int d) {
			this.ed = ed;
			this.d = d;
		}
	}

	private static void DFS(int x, int sum) {
		if (R < sum) {
			R = sum; // 현재의 최대 거리 갱신
			node = x; // 정점 번호 저장
		}

		// 유도 조건
		visited[x] = true; // 방문처리
		for (Edge e : graph[x]) {
			if (!visited[e.ed]) {
				DFS(e.ed, sum + e.d);
			}
		}
	}
}

 

 

 

참고 자료

[백준]1167: 트리의 지름 - JAVA

 

 

 

*** 그동안(두 달) 1일 1알고리즘 실천 중이었는데, 오늘부터 1일 1알고리즘 후 1일 1포스팅 도전~~~ 가보자구~~~👊🔥