[BOJ] 1967. 트리의 지름

DFS를 이용하여 트리의 구조에서 지름을 찾는 문제였다.

트리의 지름은 리프노드에서 리프노드까지의 거리를 의미하기 때문에 브루트포스의 형식으로 모든 노드를 탐색하면서 리프노드라고 판별될 경우 그 노드를 기준으로 DFS를 돌아서 다른 리프노드까지의 거리를 찾아서 비교하여 최대값을 구하는 방식으로 풀이해보았다.

package algostudy2;
 
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;
 
public class Main_bj_1967_트리의지름 {
    static class Node {
        int point, weight;
 
        public Node(int point, int weight) {
            this.point = point;
            this.weight = weight;
        }
    }
 
    static int N;
    static List<Node>[] map;
    static boolean[] visit;
    static int tempAnswer;
 
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = null;
        N = Integer.parseInt(br.readLine());
 
        map = new ArrayList[N + 1];
        for (int i = 1; i <= N; i++) {
            map[i] = new ArrayList<>();
        }
 
        for (int i = 0; i < N - 1; i++) {
            st = new StringTokenizer(br.readLine());
            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());
            int weight = Integer.parseInt(st.nextToken());
 
            map[start].add(new Node(end, weight));
            map[end].add(new Node(start, weight));
        }
 
        int answer = 0;
        for (int i = 1; i <= N; i++) {
            if (map[i].size() == 1) {        //리프노드일경우
                visit = new boolean[N + 1];
                tempAnswer = 0;
                dfs(i, 0);
                answer = Math.max(answer, tempAnswer);
            }
        }
 
        System.out.println(answer);
    }
 
    static void dfs(int cur, int distance) {
        visit[cur] = true;
 
        tempAnswer = Math.max(tempAnswer, distance);
 
        for (Node node : map[cur]) {
            int next = node.point;
 
            if (visit[next] == false) {
                dfs(next, distance + node.weight);
            }
        }
 
    }
}
 

 

하지만 위와 같이 풀이하게 되면 불필요하게 전부다 탐색을 하게 되기에 이 문제는 다음과 같은 방법을 이용하여 시간을 줄일 수가 있다. 이 문제 같은 경우 루트노드가 1번으로 보장이 되기에 1. 루트(1번노드)에서 가장 멀리떨어져있는 리프노드를 찾고 2.그 리프노드에서 가장 멀리떨어져있는 리프노드까지의 거리를 찾는 방식 으로 최대값을 구할 수 있다.

package algostudy2;
 
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;
 
public class Main_bj_1967_트리의지름_2 {
    static class Node {
        int point, weight;
 
        public Node(int point, int weight) {
            this.point = point;
            this.weight = weight;
        }
    }
 
    static int N;
    static List<Node>[] map;
    static boolean[] visit;
    static int tempDistance;
    static int deepestIndex;
 
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = null;
        N = Integer.parseInt(br.readLine());
 
        if (N == 1) {
            System.out.println(0);
            return;
        }
 
        map = new ArrayList[N + 1];
        for (int i = 1; i <= N; i++) {
            map[i] = new ArrayList<>();
        }
 
        for (int i = 0; i < N - 1; i++) {
            st = new StringTokenizer(br.readLine());
            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());
            int weight = Integer.parseInt(st.nextToken());
 
            map[start].add(new Node(end, weight));
            map[end].add(new Node(start, weight));
        }
 
        tempDistance = 0;
        deepestIndex = 0;
 
        visit = new boolean[N + 1];
        dfs(1, 0);
 
        tempDistance = 0;
        visit = new boolean[N + 1];
        dfs(deepestIndex, 0);
 
        System.out.println(tempDistance);
    }
 
    static void dfs(int cur, int distance) {
        visit[cur] = true;
 
        if (tempDistance < distance) {
            tempDistance = distance;
            deepestIndex = cur;
        }
 
        for (Node node : map[cur]) {
            int next = node.point;
 
            if (visit[next] == false) {
                dfs(next, distance + node.weight);
            }
        }
 
    }
}