[BOJ] 1167: 트리의 지름(JAVA)

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

1167번: 트리의 지름

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

입력

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

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

출력

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

예제 입력 1

5

1 3 2 -1

2 4 4 -1

3 1 2 4 3 -1

4 2 4 3 3 5 6 -1

5 4 6 -1

예제 출력 1 

11

---

[문제 풀이]

다익스트라나 플로이드와샬 알고리즘을 사용해도 해결은 가능하지만 메모리 초과가 난다..

다른 사람들의 코드를 참고하였는데 DFS, BFS 둘 다 이용해서 해결할 수 있는 방법이 있다. 

나는 DFS를 이용하여 문제를 해결하는 방법으로 풀었다.

 

해당 문제를 해결하기 위해서는 모든 정점에서 가장 먼 정점을 구하면 가중치가 가장 큰 노드가 항상 포함됨을 알아야한다. 따라서 가중치가 가장 큰 노드를 구하기 위해서는 임의의 정점에서 가장 먼 정점을 구하면 가중치가 가장 큰 노드를 구할 수 있다. 해당 노드를 max_idx에 저장한다.

 

1. dfs를 이용해 임의의 정점에서 가장 먼 정점을 구하면 이는 트리의 모든 노드 중 가중치가 가장 큰 노드가 된다.

2. 그리고 위에서 구한 정점(max_idx)에서 다시 dfs를 통해 가장 먼 정점까지의 거리를 구한다.

 

 

[코드]

import java.util.*;
class Node{
	int num;
	int cost;
	
	public Node(int num, int cost) {
		this.num= num;
		this.cost=cost;
	}
}

public class Main{
	static ArrayList<Node>[] tree;
	static boolean[] visit;
	static int max= 0, max_idx;
	
	public static void dfs(int idx, int cost) {
		
		if(cost>max) {
			max = cost;
			max_idx = idx;
		}
		
		visit[idx] = true;
		
		for(Node n:tree[idx]) {
			if(!visit[n.num]) {
				visit[n.num] = true;
				dfs(n.num,cost+n.cost);
			}
		}
	}
	public static void main(String[] args) {
         Scanner sc = new Scanner(System.in);
         int N = sc.nextInt();
         tree = new ArrayList[N+1];
         
         
         for(int i=1;i<=N;i++)
        	 tree[i] = new ArrayList<>();
     
         
         for(int i=0;i<N;i++) {
        	 int node = sc.nextInt();
        	
        	 while(true) {
        		 int child = sc.nextInt();
        		 if(child == -1)
        			 break;
        		 int cost = sc.nextInt();
        		 tree[node].add(new Node(child,cost));
        		 
        	 }
         }
         
         visit =  new boolean[N+1];
         dfs(1,0);
         visit = new boolean[N+1];
         dfs(max_idx,0);
         
         System.out.println(max);
        	 
	}
}