[백준] 1167 트리의 지름

1. 문제

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

1167번: 트리의 지름

2. 접근방법

어느 정점을 루트로 가지는 트리형태로 생각하고

백트레킹을 이용해 풀이하였음.

 

모든 정점에서 아래와 같은 작업을 해주면 된다.

1. 내 자식노드들로 부터 받은 가중치 중 가장 큰 값에 부모로 가는 가중치를 더해 return

2. 내 자식노드들로 부터 받은 가중치 중 가장 큰 값과 두번째로 큰 값의 합을 max값과 비교해 크다면 max에 저장

 

이 방식으로 풀면 어떤 정점을 루트로 가지던 상관없이 답이 나오고

한번의 탐색으로 풀이가 가능하다.

 

3. 자바 코드

package Gold;

import java.awt.*;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

public class G3_1167트리의지름 {
    static boolean visit[];
    static List<Point> [] list;
    static int max = 0;
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int V = Integer.parseInt(br.readLine());
        list = new List[V+1];
        visit = new boolean[V+1];
        for(int i = 0 ; i < V+1 ; i++) list[i] = new ArrayList<>();

        for(int i = 1 ; i < V+1 ; i++){
            StringTokenizer st = new StringTokenizer(br.readLine());
            int nn = Integer.parseInt(st.nextToken());
            while(true){
                int n = Integer.parseInt(st.nextToken());
                if ( n == -1)
                    break;
                list[nn].add(new Point(n,Integer.parseInt(st.nextToken())));
            }
        }
        visit[1] = true;
        dfs(1);
        System.out.println(max);
    }
    static int dfs(int num){
        int val = 0;
        int secVal = 0;
        for(Point p : list[num]){
            if(visit[p.x])
                continue;
            visit[p.x] = true;
            int dVal = dfs(p.x)+p.y;
            if(val<dVal) {
                secVal = val;
                val = dVal;
            }
            else if(secVal < dVal)
                secVal = dVal;
        }

        max = Math.max(max,val+secVal);
        return val;
    }
}

4. 마치며

다른 풀이들을 찾아보니

이 문제의 공식같은 풀이 방법이 있었는데

 

1. 한 정점에서 가장 먼 거리에 있는 정점 찾기

2. 그 정점에서 가장 먼 거리에 있는 정점 찾기

이렇게 2번의 탐색을 통해 정답을 구할 수 있다고 한다.