[PS] BOJ1967 트리의 지름 ( tree + dfs ) with JAVA

1967번: 트리의 지름

 

 

◎ 문제풀이

 

트리의 지름의 최대 길이를 구하는 문제이다. 이는 노드A에서 노드B까지 거리의 최댓값을 구하라는 의미이다. 한 노드에서 다른 노드까지 가는 경우의 수를 완전탐색하여 최댓값을 구하는 문제이므로 DFS를 이용하면 된다. 

 

추가로, 문제를 더 빠르게 푸는 방법이 있다. 

 

1) 1번 노드에서 DFS 완전탐색으로 가장 멀리 떨어져있는 노드A를 구한다.

2) 노드A까지 가는 경로는 가중치가 가장 높은 경로를 의미한다.

3) 노드A에서 거리가 가장 먼 노드가 트리 지름의 최댓값을 의미한다. 

 

 

 

◎ 코드

 

1. 일반 풀이

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

import static java.lang.Math.*;

//BOJ1967 트리의 지름 ( tree + dfs )
public class Main {

    static List<Edge>[] tree;
    static boolean[] isParent;
    static boolean[] visited;
    static int n, ans;

    public static class Edge{
        int next;
        int cost;

        public Edge(int next, int cost) {
            this.next = next;
            this.cost = cost;
        }
    }

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

        n = Integer.parseInt(br.readLine());
        tree = new List[n+1];
        isParent = new boolean[n+1];

        for(int i=0;i<=n;i++){
            tree[i] = new ArrayList<>();
        }

        StringTokenizer st;
        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 cost = Integer.parseInt(st.nextToken());
            
            // 양방향 관계
            tree[parent].add(new Edge(child,cost));
            tree[child].add(new Edge(parent,cost));
            
            // 부모노드, 리프노드 분리용 플래그
            isParent[parent] = true;

        }

        // 특정노드 -> 리프노드 거리 최댓값 구하기
        for(int i=1;i<=n;i++){
            visited = new boolean[n+1];
            findMaxDiameter(i,0); // DFS 탐색 
        }
        
        // 출력
        System.out.println(ans);

    }

    public static void findMaxDiameter(int node, int diameter){

        if(!isParent[node] && diameter != 0){ // 마지막 리프노드인 경우
            ans = max(ans,diameter); // 최댓값 갱신
            return;
        }

        visited[node] = true; // 양방향 관계에서 역행방지

        for( Edge edge : tree[node]){         
            if(visited[edge.next]) continue;
            findMaxDiameter(edge.next,diameter+edge.cost);
        }
    }
}

 

 

2) 빠른 풀이

package org.example.tree;

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

import static java.lang.Math.*;

//BOJ1967 트리의 지름 ( tree + dfs )
public class Tree5 {

    static List<Edge>[] tree;
    static boolean[] visited;
    static int n, ans, maxNode;

    public static class Edge{
        int next;
        int cost;

        public Edge(int next, int cost) {
            this.next = next;
            this.cost = cost;
        }
    }

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

        n = Integer.parseInt(br.readLine());
        tree = new List[n+1];

        for(int i=0;i<=n;i++){
            tree[i] = new ArrayList<>();
        }

        StringTokenizer st;
        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 cost = Integer.parseInt(st.nextToken());

            tree[parent].add(new Edge(child,cost));
            tree[child].add(new Edge(parent,cost));
            
        }
        
        visited = new boolean[n+1];
        findMaxDiameter(1,0); // 노드1 DFS 탐색
        visited = new boolean[n+1];
        findMaxDiameter(maxNode,0); // 가중치가 높은 노드 DFS 탐색

        System.out.println(ans);

    }

    public static void findMaxDiameter(int node, int diameter){
        
        if(ans < diameter){
            ans = diameter;
            maxNode = node; // 가중치 높은 노드 갱신
        }

        visited[node] = true; // 양방향 관계에서 역행방지

        for( Edge edge : tree[node] ){
            if(visited[edge.next]) continue;
            findMaxDiameter(edge.next,diameter+edge.cost);
        }
    }
    
}