[Algorithm] 백준 트리문제 - 트리의 지름(1167) 자바 풀이

안녕하세요. 회사와 함께 성장하고 싶은 KOSE입니다.

이번 포스팅은 백준 트리 문제 - 트리의 지름 자바 풀이를 진행하고자 합니다.

문제 출처: https://www.acmicpc.net/problem/1167

1167번: 트리의 지름

 

1. 풀이 소스

 

import java.util.*;
import java.io.*;
import static java.lang.Integer.parseInt;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        int n = parseInt(br.readLine());
        Graph graph = new Graph(n); // 그래프 생성
        
        for (int i = 0; i < n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int v1 = parseInt(st.nextToken()); // 첫 번째 문자 정점
            while (true) {
                int v2 = parseInt(st.nextToken()); // 연결할 정점 -1이면 종료
                if (v2 != -1) {
                    graph.addEdge(v1, v2, parseInt(st.nextToken())); // 간선 길이
                } else break;                 
            }            
        }
        
        graph.run(1,  0); // 임의의 정점에서 가장 긴 정점 구하기
        graph.run(graph.getNext(), 0); // 다음 정점에서 가장 긴 정점 구하기
        
        System.out.println(graph.getMax());
    }
}

class Graph {
    int n;
    int max; // 정점 최장 거리
    int next; // 다음에 dfs를 계산할 next 노드
    Node[] nodes; // 노드 배열
    boolean[] visited; // 방문 설정
    
    Graph(int n) {
        this.n = n;
        nodes = new Node[n + 1];
        for (int i = 1; i <= n; i++) nodes[i] = new Node(i); // 초기화
    }
    
    class Node {
        int x;
        List<Edge> edges = new ArrayList<>(); // 노드에 연결될 간선 설정
        
        Node (int x) {
            this.x = x;
        }
    }
    
    class Edge { // edge
        int y; // x 노드와 연결되는 간선 y
        int dist; // x 노드와 y 노드의 간선 길이
        
        Edge (int y, int dist) {
            this.y = y;
            this.dist = dist;
        }
    }
    
    void addEdge(int x, int y, int dist) {
        Node n1 = nodes[x];      // 단방향 간선
        n1.edges.add(new Edge(y, dist));
    }

    void run(int x, int dist) {
        visited = new boolean[n + 1]; // visited 초기화
        dfs(x, dist); // dfs 실행
    }

    void dfs(int x, int dist) {
        Node n1 = nodes[x];
        visited[n1.x] = true;

        for (Edge e : n1.edges) { // 간선 탐색
            if (!visited[e.y]) { // 간선에 연결된 노드에 방문하지 않은 경우
                dfs(e.y, dist + e.dist); // 다음 노드, 현재 거리에 간선 길이 더하기
            }
        }

        if (max < dist) { // 길이가 더 크면
            max = dist; // 길이 업데이트
            next = x; // 다음 노드 업데이트 
        }
    }
    
    int getMax() {
        return max;
    }
    int getNext() {return next;}
    
}

 

2. 풀이 중점 사항

 

트리의 지름을 구하는 알고리즘은 DFS 혹은 BFS를 두 번 탐색하여 구할 수 있습니다.

트리는 사이클이 없는 그래프이므로, 트리의 지름은 트리 상에서 가장 멀리 떨어진 두 정점의 거리입니다.

이런 특성으로 인해 한 정점에서 가장 먼 정점을 찾고 나서, 다시 그 정점에서 다시 가장 먼 정점을 찾는다면 트리의 지름을 얻을 수 있습니다.!

 

따라서, 두 번의 dfs를 통해 가장 긴 거리를 유지하는 정점을 찾고 다시 그 정점에서 가장 긴 정점을 찾는다면 문제를 해결할 수 있습니다.

 

ex)

3  - ------- - - - 1

|     \            d: 10

|      \  

|        \ d: 500

|          4

|  d: 20

2

 

1의 노드 입장에서 가장 먼 노드는 4번입니다. 하지만 4번 노드에서 가장 긴 정점은 2번 노드입니다.

즉 임의의 노드에서 가장 먼 노드를 찾고 그 노드에서 다시 한번 가장 먼 노드를 찾으면 트리의 지름을 구할 수 있습니다.

 

이상으로 트리의 지름 자바 풀이를 마치겠습니다. 감사합니다!