[백준 1167] 트리의 지름

문제

1167번: 트리의 지름

1167번: 트리의 지름

해결

트리가 주어질 때 간선의 길이가 최대로 길어질 때 그 값을 출력하는 문제이다.

접근

최대의 길이를 구하기 위해선 노드의 끝과 끝을 이은 값들 중 가장 큰 값을 출력하면 될 것이다. 시작하는 노드의 값이 끝 지점에 있는 노드임을 알 수 있다면, dfs를 사용해 각 끝노드까지의 길이를 계산해 가장 큰 값을 출력할 수 있다.

 

 

위 이미지를 예로 설명해보자면, 노드 1이 가장 끝 지점에 있으므로 dfs로 해당 노드로 dfs를 돌린다. 이렇게 되면 dfs는 노드의 끝 지점인 2 또는 5에 도달하게 될 것이고, 두 지점의 길이는 끝과 끝을 이은 간선의 값이라고 볼 수 있다.

 

두 지점의 값 중 더 큰 값을 출력하면 답이 되는 것이다.

dfs

static void dfs(int vertex, int cost) {
    if (cost > max) {
        max = cost;
        node = vertex;
    }

    visited[vertex] = true;

    for (int i = 0; i < tree.get(vertex).size(); i++) {
        Node nd = tree.get(vertex).get(i);

        if (!visited[nd.vertex]) {
            dfs(nd.vertex, nd.edgeCost + cost);
            visited[nd.vertex] = true;
        }
    }
}

 

dfs를 넘길 때, 현재 노드의 cost를 더한 값을 넘겨준다. 이렇게 넘겨주어야 현재 지점부터 끝 지점까지 간선의 길이를 알 수 있다.

그리고 max와 cost 값을 비교하며 큰 값을 최신화한다. max의 값이 간선의 합이므로 문제에서 요구하는 가장 긴 길이가 될 것이다.

끝 지점 찾기

위 까지의 로직은 시작하는 노드가 끝 지점이라는 보장이 되는 상태에서 진행했을 때 올바른 답을 찾을 수 있다. 하지만 문제에서는 끝 지점의 노드를 지정해주지 않았기 때문에 끝 지점의 노드를 찾아야 한다.

 

방법은 어렵지 않다. dfs를 두번 호출하면 된다. 만약 dfs를 시작하는 노드가 끝에 존재하는 노드가 아니라도 dfs가 종료되는 시점은 마지막 노드이기 때문에, 한번 호출 후 종료되는 시점의 노드의 값을 저장해주면 된다. 위의 코드에서 max의 값을 변경하며 node의 값까지 저장한 이유가 이것 때문이다.

 

이후에 방문한 기록(visited)들을 다시 초기화해서 찾은 node의 값을 시작으로 dfs를 진행한다면 max의 값이 가장 긴 길이가 된다.

코드

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

public class Main {

    static ArrayList<ArrayList<Node>> tree;
    static boolean[] visited;
    static int max = 0;
    static int node;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int V = Integer.parseInt(br.readLine());
        tree = new ArrayList<>();
        visited = new boolean[V + 1];

        for (int i = 0; i <= V; i++) {
            tree.add(new ArrayList<>());
        }

        StringTokenizer st;
        for (int i = 0; i < V; i++) {
            st = new StringTokenizer(br.readLine());
            int vertex = Integer.parseInt(st.nextToken());
            while (true) {
                int v = Integer.parseInt(st.nextToken());
                if (v == -1) break;
                int e = Integer.parseInt(st.nextToken());
                tree.get(vertex).add(new Node(v, e));
            }
        }

        dfs(1, 0);

        visited = new boolean[V + 1];
        dfs(node, 0);

        System.out.println(max);

    }

    static void dfs(int vertex, int cost) {
        if (cost > max) {
            max = cost;
            node = vertex;
        }

        visited[vertex] = true;

        for (int i = 0; i < tree.get(vertex).size(); i++) {
            Node nd = tree.get(vertex).get(i);

            if (!visited[nd.vertex]) {
                dfs(nd.vertex, nd.edgeCost + cost);
                visited[nd.vertex] = true;
            }
        }
    }

    static class Node {
        int vertex;
        int edgeCost;

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

 

 

 

Reference
https://moonsbeen.tistory.com/101