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

 

관련글

 

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

 

 

1. 개요

 

문제의 링크는 여기를 참조

 

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

 

트리의 지름을 구하는 문제

 

2. 풀이

 

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

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

 

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

 

 

3. 코드

 

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

 

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

public class Main{
    static int n;
    static ArrayList<Vertex>[] 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=1; i <= n; i++){
            graph[i] = new ArrayList<>();
        }
        
        for(int i=0; i < n; i++){
            st = new StringTokenizer(br.readLine());
            int u = Integer.parseInt(st.nextToken());
            while(true){
                int v = Integer.parseInt(st.nextToken());
                if(v == -1) break;
                
                int w = Integer.parseInt(st.nextToken());
                graph[u].add(new Vertex(v, w));
                graph[v].add(new Vertex(u, w));
            }
        }
        // **************************************************************
        
        // ********************** 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 u, int weight){
        visited[u] = true;
        
        // 현재까지의 가중치(거리)가 max보다 크다면 해당 가중치를 저장
        // 가중치가 업데이트 되었다면 노드도 현재 노드로 업데이트
        if(weight > max){
            max = weight;
            idx = u;
        }
        
        // 인접 노드 탐색 수행
        for(Vertex v : graph[u]){
            if(visited[v.v]) continue;
            dfs(v.v, weight + v.w);
        }
    }
}
class Vertex{
    int v;
    int w;
    public Vertex(int v, int w){
        this.v = v;
        this.w = w;
    }
}

 

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