알고리즘 풀이 - 백준 1967(트리의 지름, 트리/그래프(DFS))

 

관련글

 

트리 관련 포스팅은 여기를 참조
그래프 관련 포스팅은 여기를 참조
DFS 관련 포스팅은 여기를 참조
BFS 관련 포스팅은 여기를 참조

 

 

1. 개요

 

문제의 링크는 여기를 참조

 

문제의 내용은 아래의 더보기를 클릭하여 참조

 

트리의 지름을 구하는 문제

 

 

2. 풀이

 

트리의 지름 : 현재 트리 상의 모든 노드 간의 거리 중 가장 그 거리가 긴 것을 의미

트리의 지름을 찾는 방법은 간단하다. 특정 노드에서 가장 멀리 위치한 노드를 찾고 해당 노드에서 다시 가장 멀리 위치한 노드를 찾으면 지름을 구할 수 있다.

 

즉, 특정 하나의 노드에서 가장 먼 정점을 BFS 또는 DFS로 찾고 해당 가장 먼 노드에서 다시 BFS 또는 DFS를 통해 가장 멀리 위치한 노드를 찾아서 그 거리를 구하면 되는 문제이다.

 

 

 

3. 코드

 

아래의 코드를 통해 정답을 알아보자.

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

public class Main{
    static int n;
    static ArrayList<Edge>[] graph;
    static boolean[] visited;
    static int max = 0;
    static int idx = 0;
    public static void main(String[] args) throws IOException{
        
        // ******************** 주어진 값 저장 **************************
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        graph = new ArrayList[n+1];
        
        for(int i=0; i <= n; i++){
            graph[i] = new ArrayList<>();
        }
        
        for(int i=0; i < n-1; i++){
            st = new StringTokenizer(br.readLine());
            int parent = Integer.parseInt(st.nextToken());
            int child = Integer.parseInt(st.nextToken());
            int weight = Integer.parseInt(st.nextToken());
            
            graph[parent].add(new Edge(child, weight));
            graph[child].add(new Edge(parent, weight));
        }
        // **************************************************************
        
        
        // ********************** DFS 기반 트리 지름 찾기 수행 ***********
        visited = new boolean[n+1];
        dfs(1, 0);
        visited = new boolean[n+1];
        dfs(idx, 0);
        // **************************************************************
        
        System.out.println(max);
        
        br.close();
    }
    
    private static void dfs(int v, int w){
        visited[v] = true;
        if(w > max){
            idx = v;
            max = w;
        }
        
        for(Edge e : graph[v]){
            if(!visited[e.value]){
                dfs(e.value, w + e.weight);
            }
        }
    }
}
class Edge{
    int value;
    int weight;
    public Edge(int value, int weight){
        this.value = value;
        this.weight = weight;
    }
}

 

 

읽어주셔서 감사합니다. 오류가 있으면 지적해주시면 반영하겠습니다.