[백준]1167번 트리의 지름 - C++/Java

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

1167번: 트리의 지름

문제

트리의 지름이란, 트리에서 임의의 두 점 사이의 거리 중 가장 긴 것을 말한다. 트리의 지름을 구하는 프로그램을 작성하시오.

입력

트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2 ≤ V ≤ 100,000)둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. 정점 번호는 1부터 V까지 매겨져 있다.

먼저 정점 번호가 주어지고, 이어서 연결된 간선의 정보를 의미하는 정수가 두 개씩 주어지는데, 하나는 정점번호, 다른 하나는 그 정점까지의 거리이다. 예를 들어 네 번째 줄의 경우 정점 3은 정점 1과 거리가 2인 간선으로 연결되어 있고, 정점 4와는 거리가 3인 간선으로 연결되어 있는 것을 보여준다. 각 줄의 마지막에는 -1이 입력으로 주어진다. 주어지는 거리는 모두 10,000 이하의 자연수이다.

출력

첫째 줄에 트리의 지름을 출력한다.

---

 

    트리의 지름을 구하는 방법은 임의의 점에서 깊이 우선 탐색을 활용하여 가장 먼 점을 구하면 트리의 지름의 한 점을 구할 수 있게 된다. 이제 그 점에서 다시 가장 먼 점을 구하면 트리의 지름을 구할 수 있다. 트리의 지름을 어떻게 구할지가 포인트인 문제이다.

#include <iostream>
#include <vector>

using namespace std;
int n,a,b,c;
vector <pair<int,int>> arr[100001];
bool vis[100'001] = {0};
pair<int, int> ans;
void dfs(int node, int len) {
	vis[node] = true;
	for (auto e : arr[node]) {
		if (!vis[e.first]) {
			if (len + e.second > ans.second) {
				ans = { e.first,len + e.second };
			}
			dfs(e.first, len + e.second);
		}
	}
	vis[node] = false;
	return;
}

int main() {

	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> a;
		while (1) {
			cin >> b;
			if (b != -1) cin >> c;
			else break;
			arr[a].push_back({ b,c });
		}
	}
	ans = { 0,0 };
	dfs(1, 0);
	ans.second = 0;
	dfs(ans.first, 0);
	cout << ans.second;
}

package test;
import java.util.*;

class Pair{
	private int first;
	private int second;
	public Pair(int f,int s) {
		this.first = f;
		this.second = s;
	}
	
	public int first() {
		return this.first;
	}
	public int second() {
		return this.second;
	}
	public void setFirst(int f) {
		this.first = f;
	}
	public void setSecond(int s) {
		this.second = s;
	}
}

public class Main {
	static int n,a,b,c;
	static ArrayList<Pair>[] arr = new ArrayList[100001]; 
	static Pair ans = new Pair(0,0);
	static boolean[] vis = new boolean[100001];
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		n = sc.nextInt();
		for(int i=0;i<=n;i++) arr[i] = new ArrayList<Pair>();
		for(int i=1;i<=n;i++) {
			a = sc.nextInt();
			while(true) {
				b = sc.nextInt();
				if(b != -1) c = sc.nextInt();
				else break;
				arr[a].add(new Pair(b,c));
			}
		}
		dfs(1,0);
		ans.setSecond(0);
		dfs(ans.first(),0);
		System.out.println(ans.second());
		
	}
	
	public static void dfs(int node, int len) {
		vis[node] = true;
		for (Pair e : arr[node]) {
			if (!vis[e.first()]) {
				if (len + e.second() > ans.second()) {
					ans.setFirst(e.first());
					ans.setSecond(len + e.second());
				}
				dfs(e.first(), len + e.second());
			}
		}
		vis[node] = false;
		return;
	}
		
}

---

    트리의 지름이라는 것을 구하는 방법을 몰랐는데 이 문제를 통해 알게 되었다. 노드 별로 다 확인을 하면 분명 시간초과가 날 것 같았는데 참으로 기발한 방법이다. 다음번에도 이런 문제가 나오면 생각할 수 있을 것 같다.

    Java의 경우 Pair라는 것이 없나 검색을 해보았는데 별도로 Pair와 같은 것이 있기는 한데 오히려 복잡하고 쉽게 객체를 생성할 수 있기 때문에 Pair라는 클래스를 직접 만들어서 사용하는 것이 편해 보였다. 저번에는 ArrayList를 활용해보았는데 이번에는 ArrayList 배열을 생성해보았다. ArrayList <Integer> arr = new ArrayList [100]; 과 같이 선언한 후 사용할 만큼 arr[i] = new ArrayList <Integer>(); 과 같이 배열의 원소로 인스턴스를 지정해주면 된다. 이렇게 직접 짠 C++ 코드를 자바로 바꾸니 자바에 익숙해지는데 도움이 되는 것 같다!