(JAVA) [BOJ]백준 1167번, 트리의 지름

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

1167번: 트리의 지름

 

1167, 트리의 지름

📌 난이도 : Gold 2

📌 알고리즘 : DFS & 그래프이론

 

이번 문제는 임의의 두 점 사이의 거리 중 가장 긴 것, 지름을 구하는 문제이다. 모든 정점에 대하여 탐색을 진행하며 거리의 최대값을 구하면 되지만 정점의 개수가 100,000개 까지이다 보니 시간초과가 발생한다.그렇기에 다른 방안을 생각해보자. 임의의 정점에서 제일 멀리있는 정점의 길을 따라가다보면 항상 겹치는 부분이 존재한다.정점간 가중치를 기준으로 경로를 결정하기 때문에 가장 긴 정점의 경로는 결국 어느 정점에서 가장 먼 거리에 있는 정점의 경로와 겹칠 수 밖에 없는 것이다. 그렇기 때문에 풀이는 DFS 를 통해 임의의 정점에서 가장 먼 정점을 구하고, 그 정점에서 가장 먼 정점까지의 가중치, 즉 거리를 구하면 되는 문제이다.

 

🧩 프로세스

📚 초기화 및 선언

: 입력받은 것을 기반으로 ArrayList<Integer>[] adj 에 정점과 가중치를 선언해준다.

static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static int N,MAX,node;
static ArrayList<int[]>[] adj;
static boolean[] visit;

public static void main(String[] args) throws IOException {
    input();
    process();
}

public static void input() throws IOException {
    N = Integer.parseInt(br.readLine());

    adj = new ArrayList[N+1];
    for(int i=1; i<=N; i++) adj[i] = new ArrayList<>();

    StringTokenizer st;
    int from, to, value;
    for(int i=1; i<=N; i++) {
        st = new StringTokenizer(br.readLine(), " ");

        from = Integer.parseInt(st.nextToken());

        while(true) {;
            if((to = Integer.parseInt(st.nextToken())) == -1) break;
            value = Integer.parseInt(st.nextToken());

            adj[from].add(new int[] {to,value});
        }
    }
}

 

📚 가장 먼 정점, 그 정점부터 가장 먼 노드까지의 거리 구하기

: 임의의 정점에서 부터 가장 먼 거리를 구해야 하니 1번 정점을 기준으로 찾아준다.

그 후에 똑같은 DFS를 통해 가중치(거리)를 구한다.

public static void process() {
    // 임의의 노드(1)에서 부터 가장 먼 노드를 찾는다. 이때 찾은 노드를 node에 저장한다.
    visit = new boolean[N+1];
    DFS(1,0);

    // node에서 부터 가장 먼 노드까지의 거리를 구한다
    visit = new boolean[N+1];
    DFS(node,0);

    System.out.println(MAX);
}

public static void DFS(int start, int weight) {
    if(weight > MAX) {
        MAX = weight;
        node = start;
    }

    visit[start] = true;

    for(int[] K : adj[start]) {
        if(visit[K[0]]) continue;

        DFS(K[0], weight + K[1]);
    }
}

 

✅ 전체 코드

import java.util.*;
import java.io.*;

public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static int N,MAX,node;
    static ArrayList<int[]>[] adj;
    static boolean[] visit;

    public static void main(String[] args) throws IOException {
        input();
        process();
    }

    public static void input() throws IOException {
        N = Integer.parseInt(br.readLine());

        adj = new ArrayList[N+1];
        for(int i=1; i<=N; i++) adj[i] = new ArrayList<>();
            
        StringTokenizer st;
        int from, to, value;
        for(int i=1; i<=N; i++) {
            st = new StringTokenizer(br.readLine(), " ");

            from = Integer.parseInt(st.nextToken());

            while(true) {;
                if((to = Integer.parseInt(st.nextToken())) == -1) break;
                value = Integer.parseInt(st.nextToken());

                adj[from].add(new int[] {to,value});
            }
        }
    }

    public static void process() {
        // 임의의 노드(1)에서 부터 가장 먼 노드를 찾는다. 이때 찾은 노드를 node에 저장한다.
        visit = new boolean[N+1];
        DFS(1,0);

        // node에서 부터 가장 먼 노드까지의 거리를 구한다
        visit = new boolean[N+1];
        DFS(node,0);

        System.out.println(MAX);
    }

    public static void DFS(int start, int weight) {
        if(weight > MAX) {
            MAX = weight;
            node = start;
        }

        visit[start] = true;

        for(int[] K : adj[start]) {
            if(visit[K[0]]) continue;

            DFS(K[0], weight + K[1]);
        }
    }
}