[java] 백준 1167번 문제(트리의 지름)

원본 링크 : https://www.acmicpc.net/problem/1167

---

문제설명

 

 

소스코드

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

public class Boj_1167
{
    static class Node
    {
        int number; // 정점 번호
        int distance; // 거리

        Node(int number, int distance)
        {
            this.number = number;
            this.distance = distance;
        }
    }

    static ArrayList<Node>[] adjacencyList; // 인접 리스트
    static boolean[] visited; // 방문 배열
    static int farthestNode = 0; // 가장 멀리 있는 노드
    static int maxDistance = 0; // 가장 멀리 있는 노드의 거리

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

        int n = Integer.parseInt(br.readLine());
        adjacencyList = new ArrayList[n + 1];
        visited = new boolean[n + 1];

        for(int i = 1; i < n + 1; ++i) adjacencyList[i] = new ArrayList<>();

        for(int i = 0; i < n; ++i)
        {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int v = Integer.parseInt(st.nextToken());

            while(true)
            {
                int number = Integer.parseInt(st.nextToken());
                if(number == - 1) break;
                int distance = Integer.parseInt(st.nextToken());
                adjacencyList[v].add(new Node(number, distance));
            }
        }

        DFS(1, 0); // 임의의 정점(1)에서 가장 먼 정점 찾기

        visited = new boolean[n + 1]; // 방문 초기화
        maxDistance = 0; // 가장 먼 거리 초기화
        DFS(farthestNode, 0); // 찾은 정점에서 가장 먼 정점까지의 거리 구하기

        System.out.println(maxDistance);
    }

    // 최단 거리 찾는 것이 아니므로 DFS가 유리 함
    static void DFS(int number, int distance)
    {
        visited[number] = true; // 방문 처리

        if(distance > maxDistance) // 최고 먼 거리보다 멀다면
        {
            farthestNode = number; // 가장 먼 노드 업데이트
            maxDistance = distance; // 가장 먼 거리 업데이트
        }

        for(Node next : adjacencyList[number]) // 인접 리스트 탐색
        {
            if(!visited[next.number]) // 방문 하지 않은 곳만
            {
                DFS(next.number, distance + next.distance); // 재귀 호출
            }
        }
    }
}

 

설명

• 임의의 노드에서 가장 긴 경로로 연결되어 있는 노드는 트리의 지름에 해당하는 두 노드 중 하나다.
• 때문에 임의의 노드에서 가장 긴 경로를 탐색한다.(A 노드)
• 탐색한 경로의 노드(A노드)에서 가장 긴 경로로 다시 탐색한다.(B 노드)
• A와 B 노드 사이의 거리가 정답이다.

 

먼저 그래프를 인접 리스트로 저장한다.

노드 번호와, 거리를 표현하기 위해 노드는 클래스로 선언해야 한다.

 

DFS를 이용해서 노드 1에서부터 가장 먼 거리를 탐색한다.

 

이후 같은 방법으로 노드 5에서부터 가장 먼거리를 탐색하면 노드 1이고, 노드 5와 노드 1간의 거리는 11이다.