[Java]Baekjoon1167: 트리의 지름, 단계별 풀이

트리의 지름 

2 초

256 MB

24238

8805

6307

34.246%

문제

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

입력

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

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

출력

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

풀이

이전 백준 1967번을 통해 트리의 지름에 대한 증명을 학습했기 때문에 쉽게 풀 수 있었습니다.

1) 루트로 부터 가장 먼 노드를 구한다
2) 그 노드에서 가장 먼 노드와의 가중치가 곧 트리의 지름이다

 

트리의 연결관계 저장 방식: ArrayList + 객체

연결관계는 배열을 사용하면 메모리 낭비와 중복 탐색이 발생하므로 ArrayList 안에 저장하며, 가중치까지 같이 저장해야하므로 객체 안에 연결된 노드 번호와 가중치를 저장합니다.

static class Node{
	int num, weight;
	Node(int num, int weight){
		this.num = num;
		this.weight =weight;
	}
}

 

입력값 받기

이전과 다른점은 입력 방식 뿐입니다. 하지만 트리의 경우 개념 조건에 따라 모두 연결되어있기 때문에 각 정점에 대해 간선이 최소 하나가 존재합니다.

	for(int i=1;i<=node;i++) {
		st = new StringTokenizer(br.readLine()); // 토크나이저로 받아주고
		int num = Integer.parseInt(st.nextToken()); // 맨 앞 숫자를 가져옵니다
		int v = (st.countTokens()-1)/2; // 나머지 토큰의 개수는 -1을 포함해 홀수개입니다

		
        while(v-->0) { //트리의 연결관계를 넣어줍니다
			tree[num].add(new Node(Integer.parseInt(st.nextToken()),Integer.parseInt(st.nextToken())));
		}
        
	}

 

탐색법: DFS + 방문체크

dfs와 방문체크를 같이 적용해야하며 가중치의 최대값이 갱신될 때 그 노드의 번호를 가져와야 합니다(트리 지름 증명을 활용).

static void dfs(int n, int sum) {
	check[n] = true;
	if(MAX<sum) { //가중치의 최대값이 갱신될 때 노드 번호를 가져옵니다
		MAX = sum;
		idx = n;
	}
	//연결된 노드 중 방문하지 않은 곳을 가중치를 더하고 들어갑니다
	for(int i=0;i<tree[n].size();i++) {
		if(!check[tree[n].get(i).num]) {
			dfs(tree[n].get(i).num,sum+tree[n].get(i).weight);
		}
	}
}

 

전체 풀이

import java.io.*;
import java.util.*;
public class Main {
	static int MAX,idx;
	static ArrayList<Node>[] tree;
	static boolean[] check;
	static class Node{
		int num, weight;
		Node(int num, int weight){
			this.num = num;
			this.weight =weight;
		}
	}
	static void dfs(int n, int sum) {
		check[n] = true;
		if(MAX<sum) {
			MAX = sum;
			idx = n;
		}
		for(int i=0;i<tree[n].size();i++) {
			if(!check[tree[n].get(i).num]) {
				dfs(tree[n].get(i).num,sum+tree[n].get(i).weight);
			}
		}
	}
	public static void main(String[] args) throws IOException {
	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	StringTokenizer st;
	int node = Integer.parseInt(br.readLine());
	tree = new ArrayList[node+1];
	check = new boolean[node+1];
	for(int i=0; i<node+1;i++) {
		tree[i] = new ArrayList<>();
	}
	for(int i=1;i<=node;i++) {
		st = new StringTokenizer(br.readLine());
		int num = Integer.parseInt(st.nextToken());
		int v = (st.countTokens()-1)/2;
		while(v-->0) {
			tree[num].add(new Node(Integer.parseInt(st.nextToken()),Integer.parseInt(st.nextToken())));
		}
	}
	dfs(1,0);
	check = new boolean[node+1];
	dfs(idx,0);
	System.out.println(MAX);
}}