[백준] 1167 트리의 지름 - DFS(깊이우선탐색) + 트리(Tree) + 시간초과 JAVA

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

1167번: 트리의 지름

코드설명

DFS + 트리 + 시간초과 문제입니다.

( 다익스트라를 활용해도 풀 수 있습니다만 시간초과가 나옵니다. )

 

이 문제 같은경우 1967 트리의 지름과 매우 유사하지만, V의 크기가 더 크기에 시간초과를 고려해야합니다.

 

이 문제의 단순 시간복잡도를 계산할경우 각 모든 정점에 대해서의 최대거리값을 계산한다면, O(V^2) 입니다. 

즉, 1->3->4->5 == 11

 2->4>5 = 10

3->4->5 = 9

4->5 = 6

5-> 1 = 1

 

만약 DFS를 5번 다 돌릴시에는 11 이 될 것 입니다.

만약에 정점의 개수 V가 100000 개라면, 각 DFS의 시간이 O(V) 에다가 V개를 모두 순회하기에 O(V^V) 입니다.

시간초과가 발생합니다. 

 

 

우선 문제의 시간복잡도를 줄이기 위해서는 트리의 특성을 알야아합니다.

트리

- 싸이클이 없이 연결되어 있습니다.

- 한정점에서 다른 정점으로 가는 경로가 유일합니다. 그렇기에 가장 멀리있는 두 정점의 경로는 항상 유일합니다.

- 한 정점에서 가장 먼 정점으로 가는 경로와 가장 먼 정점 사이의 겨오는 항상 일부가 겹칩니다. 

 

1. 즉, 임의의 정점 1에서 DFS를 통해 가장 먼 다른 노드를 구합니다. 이떄 문제예시에서는 5가 나옵니다.

2. 해당 5 의 위치에서 최대 지름을 구하면 2번만의 DFS로 답을 구할 수 있습니다.

 

1->3->4->5 == 11

 2->4>5 = 10

3->4->5 = 9

4->5 = 6

5-> 1 = 1

 

이떄 보면 모든 정점에서 5 혹은 1 이 시작점이거나 마지막 점인것을 알 수 있습니다.

이를 활용하여 어떤 정점에서든 목표 종료지점을 구한뒤 해당 지점에서 DFS를 돌리면 답을 구할 수 있습니다.

코드

트리의 지름 DFS의 특성을 활용하여 해결

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
import java.util.regex.Pattern;

public class Main {
	public static int N, M;
	public static int answer = 0;
	public static ArrayList<ArrayList<Node>> graph = new ArrayList<>();
	public static boolean[] visited;
	public static int nodeIdx = 0;
	
    public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer st = new StringTokenizer(br.readLine());
    	
    	N = Integer.parseInt(st.nextToken());
    	visited = new boolean[N+1];
    	for(int i=0;i<=N;i++) {
    		graph.add(new ArrayList<Node>());
    	}
    	
    	for(int i=0; i<N;i++) {
    		st = new StringTokenizer(br.readLine());
    		int idx = Integer.parseInt(st.nextToken());
    		
    		while(true) {
    			int vIndex = Integer.parseInt(st.nextToken());
    			if(vIndex  == -1)
    				break;
    			int dist = Integer.parseInt(st.nextToken());
    			graph.get(idx).add(new Node(vIndex, dist));
    		}
    	}
    	
    	//DFS를 통해 가장 긴 길이를 찾습니다.
		visited = new boolean[N+1];
		visited[1] = true;
		simulate(1, 0);
    	
		visited = new boolean[N+1];
		visited[nodeIdx] = true;
		simulate(nodeIdx, 0);
    	
    	System.out.println(answer);
    }
    
    public static void simulate(int startIdx, int distance) {
    	if( answer < distance ) {
    		answer = distance;
    		nodeIdx = startIdx;
    	}
    	
    	for(int i=0;i<graph.get(startIdx).size();i++) {
    		Node temp = graph.get(startIdx).get(i); //연결된 다른 그래프입니다.
    		int idx = temp.index;
    		int dist = temp.distance; //다음 Index 거리
    		if(visited[temp.index] == false) {
    			visited[temp.index]= true; 
    			simulate(idx, distance + dist);
    		}
    	}
    	
    }
}

class Node{
	int index;
	int distance;
	public Node(int index, int distance) {
		this.index = index;
		this.distance = distance;
	}
}

 

 

시간초과 나는 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
import java.util.regex.Pattern;

public class Main {
	public static int N, M;
	public static int answer = 0;
	public static ArrayList<ArrayList<Node>> graph = new ArrayList<>();
	public static boolean[] visited;
	
    public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer st = new StringTokenizer(br.readLine());
    	
    	N = Integer.parseInt(st.nextToken());
    	visited = new boolean[N+1];
    	for(int i=0;i<=N;i++) {
    		graph.add(new ArrayList<Node>());
    	}
    	
    	for(int i=0; i<N;i++) {
    		st = new StringTokenizer(br.readLine());
    		int idx = Integer.parseInt(st.nextToken());
    		
    		while(true) {
    			int vIndex = Integer.parseInt(st.nextToken());
    			if(vIndex  == -1)
    				break;
    			int dist = Integer.parseInt(st.nextToken());
    			graph.get(idx).add(new Node(vIndex, dist));
    		}
    	}
    	
    	//DFS를 통해 가장 긴 길이를 찾습니다.
    	for(int i=1;i<=N;i++) {
    		visited = new boolean[N+1];
    		visited[i] = true;
    		simulate(i, 0);
    	}
    	
    	
    	System.out.println(answer);
    }
    
    public static void simulate(int startIdx, int distance) {
    	answer = Math.max(answer,  distance);
    	
    	for(int i=0;i<graph.get(startIdx).size();i++) {
    		Node temp = graph.get(startIdx).get(i); //연결된 다른 그래프입니다.
    		int idx = temp.index;
    		int dist = temp.distance; //다음 Index 거리
    		if(visited[temp.index] == false) {
    			visited[temp.index]= true; 
    			simulate(idx, distance + dist);
    		}
    		
    	}
    	
    }
}

class Node{
	int index;
	int distance;
	public Node(int index, int distance) {
		this.index = index;
		this.distance = distance;
	}
}