20180822 8월 BOJ 풀이 : 트리의 지름

트리의 지름

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

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

트리에 대해서 안다고 하지만 막상 문제를 풀어보면 모르는게 맞다. 문제에서 정의하는 트리의 지름이란 하나의 정점에서 다른 정점까지의 거리를 트리의 지름이라고 칭하고 해당 지름 중 가장 큰 지름의 값을 구하는 것이 문제였다.

항상 문제는 어렵기 때문에 고민을 어느정도 하고 답을 살펴본다. dfs 에 대한 문제였고 이 문제가 말하는 것은 해당 지름이 루트를 거치냐 혹은 거치지 않냐 두 가지로 나뉠 수가 있었다. 

예를 들어 트리가 하나 주어졌다고 상상하자.

그럼 트리에는 루트가 있고 루트 하위에는 서브트리가 여러 개 존재할 것이다.  그럼 트리의 지름은 서브트리를 고려했을때 두 가지 경우로 생각할 수 있다.

1) 서로 다른 서브트리에서 두 개의 정점을 추출하고 서로 간의 거리를 구한 경우

2) 하나의 서브트리 내에서 두 개의 정점을 추출하고 서로 간의 거리를 구한 경우

1의 경우에는 루트를 거리를 구하는 와중에 루트를 거치지만 

2의 경우에는 거치지 않는다.

결국 하나의 정점의 하위 서브트리에서의 정점간의 거리를 구하는 것이 주 핵심이고, 정점의 거리는 결국 두 개로 표현할 수 있다. 루트에서 왼쪽 정점으로의 거리1, 루트에서 오른쪽 정점으로의 거리2

import java.io.*;
import java.math.BigInteger;
import java.util.*;
 
public class Main {
 
    static InputStreamReader isr;
    static BufferedReader br;
    static OutputStreamWriter osw;
    static BufferedWriter bw;
    static StringTokenizer st;
    
    static ArrayList<ArrayList<Vertex>> list = new ArrayList<ArrayList<Vertex>>();
    static boolean visited[] = null;
    static int d = 0;
    
    public static void main(String[] args) throws IOException {
        isr = new InputStreamReader(System.in);
        br = new BufferedReader(isr);
        osw = new OutputStreamWriter(System.out);
        bw = new BufferedWriter(osw);
 
        int V = Integer.parseInt(br.readLine());
        visited = new boolean[V+1];
        
        for(int i = 0; i <= V; i++)
            list.add(new ArrayList<Vertex>());
        
        for(int i = 0; i < V; i++){
            
            st = new StringTokenizer(br.readLine());
            
            int sv = Integer.parseInt(st.nextToken());
 
            while(st.hasMoreTokens()){
                int ev = Integer.parseInt(st.nextToken());
                
                if(ev == -1)
                    break;
                
                int cost = Integer.parseInt(st.nextToken());
                
                list.get(sv).add(new Vertex(ev, cost));
            }
        }// input
        
        visited[1] = true;
        dfs(1);
        
        bw.write(d + "\n");
        bw.close();
        br.close();
    }
    
    // (1) 루트로부터 가장 멀리 떨어진 subTree 각각 두 개의 거리
    // (2) 같은 subTree 내에서의 두 개의 거리
    // sv와 가장 먼 정점의 dist 획득
    private static int dfs(int sv){
        
        int max1 = 0;    // 가장 먼
        int max2 = 0;    // 두번째로 먼
        
        for(int eIndex = 0; eIndex < list.get(sv).size(); eIndex++){
            Vertex vertex = list.get(sv).get(eIndex);
            
            // 방문
            if(visited[vertex.ev])
                continue;
            
            visited[vertex.ev] = true;
            int dist = dfs(vertex.ev) + vertex.cost;
            
            // dist 가 제일 크면
            if(dist > max1){
                max2 = max1;
                max1 = dist;
            }
            
            // dist 가 두번째로 크면
            else if(dist > max2){
                max2 = dist;
            }
        }
        
        // 루트로부터 떨어진 두 개의 간선 합 => d
        d = Math.max(d,  max1+max2);
 
        return max1;
    }
}
 
class Vertex{
    int ev;
    int cost;
    
    public Vertex(int ev, int cost){
        this.ev = ev;
        this.cost = cost;
    }
}

참고링크

http://baaaaaaaaaaaaaaaaaaaaaaarkingdog.tistory.com/143