백준 1167번 자바☆

문제

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

1167번: 트리의 지름

 

1. DFS로 가능한가?

시간복잡도를 계산하면 V의 범위가 100,000까지기 때문에 최악복잡도는 O(N2) = 약 100억으로 예상된다. 그래서 일반적인 DFS방식으로 풀면 시간초과가 발생한다.

 

2. 어떻게 접근할 것인가?

한 줄로 요약하면

임의 노드에서 가장 긴경로로 연결돼 있는 노드는 가장 긴 경로(트리의 지름)의 두 노드 중 하나이다.

예제를 그림으로 보도록하자.

그림에서 보듯 임의의 시작점에서 가장 먼 경로의 가장 먼 노드는 트리의 지름에 해당하는 두 노드 중 하나이다.

간단하게 생각해보면 트리라는 자료구조의 특성상 간선으로만 이동을 할 수 있고 중복이 안되기 때문에 가장 긴 경로의 두 노드중 한곳을 반드시 마지막노드로 할  수 밖에 없다.

 

3. 구현

import java.util.*;
import java.io.*;

public class Main1167 {

	static int V;
	static Map<Integer, Integer>[] tree;
	static boolean[] visited;
	static int max;
	static int maxNode;
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		V = Integer.parseInt(br.readLine());
		tree = new HashMap[V+1];
		visited = new boolean[V+1];
		
		for (int i=1; i<=V; i++) {
			tree[i] = new HashMap<Integer, Integer>();
		}
		
		for (int i=1; i<=V; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			int idx = Integer.parseInt(st.nextToken());
			
			for (int j=0; j<V; j++) {
				int tempKey = Integer.parseInt(st.nextToken());
				if (tempKey == -1) {
					break;
				}
				int tempVal = Integer.parseInt(st.nextToken());
				tree[idx].put(tempKey, tempVal);
			}
		}
		
		dfs(1, 0);
		visited = new boolean[V+1];
		dfs(maxNode, 0);
		
		System.out.println(max);
	}
	
	public static void dfs(int node, int distance) {
		visited[node] = true;
		if (max < distance) {
			max = distance;
			maxNode = node;
		} 
		Iterator<Integer> tempKey = tree[node].keySet().iterator();
		
		while (tempKey.hasNext()) {
			int temp = tempKey.next();
			if (!visited[temp]) {
				dfs(temp, distance + tree[node].get(temp));
			}
		}
	}
}

 

정리 : 단순 dfs구현 문제라 생각하고 접근했으나 시간초과에서 많이 헤맸다. 결과를 놓고보면 이해하기 어렵지 않았으나 처음부터 핵심개념을 생각하긴 쉽지않았다. 더 많은 문제를 풀며 경험을 늘려야겠다.