[백준] 1967 트리의 지름 - 골드4, DFS + 트리(Tree) 자바

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

1967번: 트리의 지름

 

 

 

문제해설

첫번쨰, 문제풀이방식

처음에 문제를 보고 다익스트라로 풀려는 생각이 가장 먼저 들었습니다.

이유는 트리의 간선에 가중치가 붙어있었기에 문제에서 그래프에서 가중치가 붙어있는 것이 떠올랐고, 다익스트라를 활용하여 한 점에서 한점까지의 최대 거리를 구한뒤 그것의  MAX 값을 구할려고했습니다.

하지만, 이렇게 할경우 시간초과가 납니다. 다익스트라의 시간복잡도는 한점에서 시작하였을떄 O(n log n ) 입니다.

우리는 모든 점에 대하여 각각 다익스트라를 구해야하기에 문제의 조건에 

노드의 개수 n(1 ≤ n ≤ 10,000) 에 따라서, O(n^2 log n) 으로 됩니다. 그러므로 시간초과가 나올 수 있습니다.

또한, 입력값의 범위가 10,000 x 10,000 = 1억입니다. 일반적으로 1억을 계산하는데는 1초가 걸리므로 딱 O(n^2)으로 해야만 시간이 통과할 수 있습니다.

 

문제의 유형을 보고 어떤 문제인지 대충 알아내는 팁은,

1. 그래프일경우

- 간선의 가중치가 모두 동일한 경우( 0 , 혹은 다른 숫자도 가능, 다 똑같은 크기이기에) 에는 BFS

- 간선의 가중치가 존재하는 경우 다익스트라 를 통해 한점에서 한점까지의 최단거리를 구할 수 있습니다.

 

2. 트리인경우 (싸이클이 없는경우 무방향 그래프의 경우)

- DFS (싸이클이 없기에 DFS를 사용하여도 무한루프에 걸릴 문제없다.)

- BFS (싸이클이 없기에 BFS를 사용하여도 무한루프에 걸릴 문제없다.)

 

 

다시 문제풀이로 돌아가서, 

루트노드(1번)을 기준으로 가장 거리가 먼 정점을 찾습니다. 

그 정점을 찾았다면 다시 그 정점을 기준으로 가장 거리가 먼 정점을 찾으면 그것이 지름입니다.

 

그러한 방법도 있지만, 결국 지름이라는 것이 한 노드에서 다른 노드까지 최대거리인 길이가 지름입니다.

그러므로 아래와 같이 DFS를 통해서 모든 점을 시작점으로 하여 각 점까지의 거리가 최대인것이 지름입니다.

for(int i=1;i<=N;i++) {
    visited = new boolean[N+1];
    visited[i] = true;
    dfs(i,0);
}

static void dfs(int start, int weight) {
    for(int i=0;i<tree.get(start).size();i++) {
        if(visited[tree.get(start).get(i).index] == false) {
            visited[tree.get(start).get(i).index] = true;
            dfs(tree.get(start).get(i).index, tree.get(start).get(i).distance + weight);
        }
    }
    if(answer < weight) answer = weight;
}

 

 

 

두번쨰, Scanner를 사용하면 시간초과가 나서 BufferedReader를 사용합니다.

 

 

코드입니다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class Main {
	static ArrayList<ArrayList<Node>> tree = new ArrayList<ArrayList<Node>>();
	static boolean[] visited;
	static int answer =0;
	public static void main(String[] args) throws IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		
		int N = Integer.parseInt(in.readLine());
		for(int i=0;i<=N;i++) {
			tree.add(new ArrayList<Node>());
		}
		
		for(int i=0;i<N-1;i++) {
			StringTokenizer st = new StringTokenizer(in.readLine());
			int start = Integer.parseInt(st.nextToken());
			int dest = Integer.parseInt(st.nextToken());
			int dist = Integer.parseInt(st.nextToken());
			tree.get(start).add(new Node(dest, dist));
			tree.get(dest).add(new Node(start, dist));
		}
		
		for(int i=1;i<=N;i++) {
			visited = new boolean[N+1];
			visited[i] = true;
			dfs(i,0);
		}
		System.out.println(answer);
		
	}
	
	static void dfs(int start, int weight) {
		
		for(int i=0;i<tree.get(start).size();i++) {
			if(visited[tree.get(start).get(i).index] == false) {
				visited[tree.get(start).get(i).index] = true;
				dfs(tree.get(start).get(i).index, tree.get(start).get(i).distance + weight);
			}
		}
		if(answer < weight) answer = weight;
	}
	
	static class Node{
		int index;
		int distance;
		Node(int index, int distance){
			this.index = index;
			this.distance = distance;
		}
	}
	

}