BOJ) 트리의 지름 (1167 번)

트리의 지름

1167번: 트리의 지름

이전에 포스팅했던 트리의 지름과 조금 다르게 풀었다.

먼저, 트리기 때문에 어떤 지점에서 시작해도 특정 지점까지 모두 도달할 수 있다는 특징이 있다.

이 말인 즉, 가장 멀리있는 한 특정 지점을 찾을 수 있다는 말이 된다.

 

위의 조건에 따라, 1에서 가장 먼 vertex를 찾아주었다.

이후, 해당 vertex에서 가장 먼 거리에 있는 지점을 찾으며 최댓값을 갱신해주었다.

(만약, 1 -> 찾은 지점이 가장 먼 거리라면, 찾은 지점 -> 1을 탐색하며 같은 최댓값을 가짐)

 

기술적인 특징이 있지는 않지만, 처음 접근이 어려웠던 문제라 위의 개념을 기억하기 위해 기록한다.

 

코드

 

package remindBOJ;

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

public class TreeDiameter_1167 {
    static ArrayList<Node>[] tree;
    static int answer, maxIdx;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int v = Integer.parseInt(br.readLine());
        final int END = -1;
        initTree(v);

        for(int i=0; i<v; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int left = Integer.parseInt(st.nextToken());
            while(st.hasMoreTokens()) {
                int right = Integer.parseInt(st.nextToken());
                if(right == END) {
                    break;
                }
                int weight = Integer.parseInt(st.nextToken());
                tree[left].add(new Node(right, weight));
            }
        }

        br.close();
        solution(v);
    }

    private static void initTree(int v) {
        tree = new ArrayList[v+1];
        for(int i=1; i<=v; i++) {
            tree[i] = new ArrayList<>();
        }
    }

    private static void solution(int v) {
        boolean[] visit = new boolean[v+1];
        visit[1] = true;
        dfs(1, visit, 0);
        visit[1] = false;
        visit[maxIdx] = true;
        dfs(maxIdx, visit, 0);

        System.out.println(answer);
    }

    private static void dfs(int idx, boolean[] visit, int weight) {
        for(Node node : tree[idx]) {
            if(!visit[node.vertex]) {
                visit[node.vertex] = true;
                dfs(node.vertex, visit, weight + node.weight);
                visit[node.vertex] = false;
            }
        }
        if(weight > answer) {
            answer = weight;
            maxIdx = idx;
        }
    }


    private static class Node {
        int vertex, weight;

        public Node(int vertex, int weight) {
            this.vertex = vertex;
            this.weight = weight;
        }
    }
}